100以下の素数

N = 100以下の素数をリストアップする。

#include <gmp.h>

int main(void)
{
    unsigned int N = 100UL;
    mpz_t p;
    mpz_init_set_ui(p, 2UL);
    do {
        gmp_printf("%Zd ", p);
        mpz_nextprime(p, p);
    } while (mpz_cmp_ui(p, N) <= 0);
    gmp_printf("\n");
    mpz_clear(p);
    return 0;
}

2 3 5 7 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

関数mpz_nextprimeは内部で確率的な素数判定を行っているが、
合成数を素数と誤って判定する確率は非常に小さくなるように設定されている。
もし、関数mpz_probab_prime_pと同様のものが使われているのなら、
表題のような小さな整数に対しては確率的でなく確定的に判定されるだろう。
以下のように変更してみると、

...snip
    do {
        gmp_printf("%Zd(%d) ", p, mpz_probab_prime_p(p, 25));
        mpz_nextprime(p, p);
    } while (mpz_cmp_ui(p, N) <= 0);
...snip

2(2) 3(2) 5(2) 7(2) 11(2) 13(2) 17(2) 19(2) 23(2) 29(2) 31(2) 37(2) 41(2) 43(2)
 47(2) 53(2) 59(2) 61(2) 67(2) 71(2) 73(2) 79(2) 83(2) 89(2) 97(2)

mpz_probab_prime_pの戻り値の2は確定的に素数である*1ことを示している。
判定の確率的精度を指定する25という値はGMPのリファレンスでreasonableとされる値である。
たとえmpz_nextprimeの素数の識別法がmpz_probab_prime_pと異なっていたとしても、
mpz_nextprimeも同程度の確率的精度でもって識別しているのだと思うので、
多分この程度の小さな整数に対してはmpz_nextprimeも確定的と言ってよいのではと思う。
まあそのあたりはGMPライブラリのソースを読めば分かるだろうけれど。

*1:1なら確率的に素数、0なら確定的に合成数。素数を合成数と誤判断することはない。