素数判定プログラム2 C言語GMPライブラリ の続きです。

GMPライブラリを使って素数判定プログラムを書いていきます。

gmpには素数を判定する関数が用意されています。

int mpz_probab_prime_p(mpz_t n, int reps);

戻り値で素数かどうかを判定します。

2が帰ってきたときは絶対素数 (definitely prime)
1のときは素数っぽい、(probably prime)
0のときは合成数つまり素数ではない、です。

repsはミラーラビン法のパラメータですが、通常25を指定しておけばいいそうです。

実行してみてください。一瞬で計算が終わりますよ。

$ gcc prime4.c -o prime4 -lgmp

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <gmp.h>

int main(void)
{
mpz_t number;
int answer = 0;

  mpz_init(number);

mpz_set_str(number, "940461086986004843694934910131104208392131088686023657900173332902199657733778583489", 10);
 
answer =  mpz_probab_prime_p(number, 25); 

mpz_out_str(stdout, 10, number);
if (answer) {
printf(" は素数だよ\n");
} else {
printf(" は素数じゃないよ\n");
}
return 0;
}