Apr 22, 2008
Простые числа от 2 до 1,000,000
Список простых чисел от двух до миллиона
В поисках простых чисел Софи Жермен написал программу, которая ищет простые числа (я их собирался использовать для реализации решета). От нечего делать я пошёл дальше и решил найти все простые числа до миллиона. А также проверить утверждение, что сумма всех простых чисел до миллиона есть простое число.
Программа сама по себе получилась очень простой:
[-]
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;
}
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 простых чисел до миллиона, если я правильно посчитал 
Скачать список всех простых чисел от двух до миллиона.
Простые числа Софи Жермен от двух до миллиона.