Ars Longa, Vita Brevis

Апр 22, 2008

Простые числа от 2 до 1,000,000

Рубрика: C/C++
Метки: ,
Vladimir @ 8:11 пп
RSS 2.0

Список простых чисел от двух до миллиона

В поисках простых чисел Софи Жермен написал программу, которая ищет простые числа (я их собирался использовать для реализации решета). От нечего делать я пошёл дальше и решил найти все простые числа до миллиона. А также проверить утверждение, что сумма всех простых чисел до миллиона есть простое число.

Программа сама по себе получилась очень простой:

[-]
View Code C
#include <gmp.h>

int main(int argc, char** argv)
{
    mpz_t x;
    mpz_t s;
    mpz_init_set_ui(x, 2);
    mpz_init_set_ui(s, 0);
    do {
        mpz_add(s, s, x);
        gmp_printf("%Zd\n", x);
        mpz_nextprime(x, x);
    } while (mpz_cmp_ui(x, 1000000) < 0);

    gmp_printf("%Zd: ", s);
    if (mpz_millerrabin(s, 256)) {
        gmp_printf("yes\n");
    }
    else {
        gmp_printf("no\n");
    }

    return 0;
}

Сборка:

[-]
View Code Bash
gcc primes.c -O3 -lgmp -o primes

Сумма всех простых чисел от 2 до 1,000,000 равна 37,550,402,023 и действительно является простым числом.

Кстати, всего 78,498 простых чисел до миллиона, если я правильно посчитал :-)

Скачать список всех простых чисел от двух до миллиона.

Добавить в закладки
  • del.ici.ous
  • Digg
  • Furl
  • Google
  • Simpy
  • Spurl
  • Y! MyWeb
  • БобрДобр
  • Мистер Вонг
  • Яндекс.Закладки
  • Текст 2.0
  • News2
  • AddScoop
  • RuSpace
  • RUmarkz
  • Memori
  • Закладки Google
  • Писали
  • СМИ 2
  • Моё Место
  • Сто Закладок
  • Ваау!
  • Technorati
  • RuCity
  • LinkStore
  • NewsLand
  • Lopas
  • Закладки - I.UA
  • Connotea
  • Bibsonomy
  • Trucking Bookmarks
  • Communizm
  • UCA

Комментарии к статье "Простые числа от 2 до 1,000,000" (1) »

  1. #1

RSS лента комментариев к этой записи. TrackBack URL

Оставить комментарий к записи "Простые числа от 2 до 1,000,000"

XHTML: Вы можете использовать эти теги: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>

Оставляя комментарий, Вы выражаете своё согласие с Правилами комментирования.

Подписаться, не комментируя