素数判定プログラム C言語の続きです。

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

GMPプログラミング初めてです。

ぶっつけ本番でも大丈夫でしょう。

変数をそれぞれ保存しないといけないのでプログラムが汚くなってしまいました。

C言語風のコメントも書いておきました。見づらくなったかも。w

GMPライブラリーもマスター出来ました。

//$ gcc prime3.c -o prime3 -lgmp

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

int isPrime(mpz_t number)
{
mpz_t i, four, twomod, threemod, sqrt, tmpmod, tmpmod2, iplus2;

mpz_init(i);
mpz_set_str(i, "5", 10); //10進数 5で初期化 i = 5;

mpz_init(sqrt);
mpz_sqrt(sqrt, number); 

mpz_init(four);
mpz_set_str(four, "4", 10);//10進数 4で初期化 four = 4;
mpz_init(twomod);
mpz_set_str(twomod, "0", 10);//10進数 0で初期化 twomod = 0;

mpz_init(threemod);
mpz_set_str(threemod, "0", 10);//10進数 0で初期化 threemod = 0;

mpz_init(tmpmod);
mpz_init(tmpmod2);
mpz_init(iplus2);

mpz_mod_ui(twomod, number, 2); //twomod = number % 2;
mpz_mod_ui(threemod, number, 3); //threemod = number % 3;

if (mpz_cmp_ui(number, 1) > 0 && 0 < mpz_cmp(four, number)) {
return 1;
} else if (mpz_get_ui(twomod) == 0 || mpz_get_ui(threemod) == 0) {
return 0;
} else {
for (i; 0 <= mpz_cmp(sqrt, i); mpz_add_ui(i, i, 6)) {
mpz_mod(tmpmod, number, i); //tmpmod = number % i;
mpz_add_ui(iplus2, i, 2); //iplus2 = i + 2;
mpz_mod(tmpmod2, number, iplus2); //tmpmod2 = number % iplus2;
if (mpz_get_ui(tmpmod) == 0 || mpz_get_ui(tmpmod2) == 0) {
return 0;
}
}
}

mpz_clear(i);
mpz_clear(sqrt);
mpz_clear(four);
mpz_clear(twomod);
mpz_clear(threemod);
mpz_clear(tmpmod);
mpz_clear(tmpmod2);
mpz_clear(iplus2);
return 1;
}

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

  mpz_init(number);

mpz_set_str(number, "150094772735952593", 10);

answer = isPrime(number);

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

150094772735952593 は18桁の素数です。

ここに判定する数字を入力してください。
 
素数サンプル 楽勝レベル
31389448217
282437925089
1853028778786433
5559077746424707
150094772735952593

PCだと厳しい 一気に時間がかかります。終わらないかもね。
8862938260389989451257
26588814640432479998443

実はGMPライブラリには素数を判定する関数が用意されています。

それを呼べば一発で素数かどうかを判定することができます。

次回に続きます。 素数判定プログラム3 C言語GMPライブラリ

参考サイト
多倍長整数演算ライブラリ (GNU MP) 

素数一覧 1000万 

素数表