Ars Longa, Vita Brevis

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

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

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

[-]
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
<