2023年になりました。2023 に関係する計算をしてみます。
Prime Curios! から
素数に関して、興味深い事実を多く掲載している Prime Curios! で2023を調べてみます。以下が該当しました。サイトは英語ですが、日本語に訳しました。
素数 813258173412030282336987547007 の後ろに、ちょうど 2023 個の合成数が続く。この素数は、2023 個の合成数が後に続く最小の数となる。
https://primes.utm.edu/curios/page.php?short=2023
擬素数を判定する
813258173412030282336987547007 は、30桁もあります。素数判定を行う、Baillie–PSW の素数テストと呼ばれる方法があります。この判定方法は、以下の性質を持ちます。
- 合成数と判定されれば、その数は合成数
- 素数と判定されても、その数が合成数であることがある（擬素数）。
C や C++ で多倍長演算を行うことができる GMP（GNU Multi-Precision）ライブラリがこの判定方法を関数として提供しています。なお、GMP については、この記事で紹介しています。
mpz_probab_prime_p
以下が、GMP が提供している関数 mpz_probab_prime_p の仕様です。
引数
- n : GMP が提供している多倍長の整数型の変数
- reps : Baillie–PSW の繰り返し回数
戻り値
- 2 : 素数と判定
- 1 : 擬素数と判定
- 0 : 合成数と判定
仕様
- n の素数判定を行う。数が大きくなると Baillie–PSW を使って判定する。
- 擬素数と判定された場合、それが合成数である確率は、4-reps 以下となる。計算速度と誤る確率を考慮すると reps は、15 から 50 の値が良い。（GMP マニュアルより）
素数判定プログラム（Baillie–PSW 版）
上記、関数を使って素数判定をするプログラムを作りました。どれだけ大きな数でも判定できます。繰り返し数 reps は、50 としました。誤って合成数を素数と判定する確率は、かなり低くなります。趣味で計算する場合、ほぼ 0 と考えています。
判定したい数は、プログラムの最初の引数で与えるか、標準入力で与えます。
#include <stdio.h>
#include <gmp.h>
#define REPS 50
int main(int argc, char *argv[])
{
int ret;
mpz_t z;
mpz_init(z);
if (argc > 1) {
mpz_set_str(z, argv[1], 10);
} else {
mpz_inp_str(z, stdin, 10);
}
ret = mpz_probab_prime_p(z, REPS);
mpz_out_str(stdout, 10, z);
if (ret == 2) {
printf(" is prime number.\n");
} else if (ret == 1) {
printf(" may be prime number.\n");
} else {
printf(" is composite number.\n");
}
mpz_clear(z);
return 0;
}GMP ライブラリをリンクする必要があります。gcc を使う場合は、以下のコマンドとなります。
gcc -o isPrime_gmp isPrime_gmp.c -lgmp2023 について追試験する
813258173412030282336987547007 から 2023 個合成数が続くことを確認してみました。
#include <stdio.h>
#include <gmp.h>
#define REPS 50
char number[] = "813258173412030282336987547007";
int main(int argc, char *argv[])
{
int i;
int ret;
mpz_t z;
mpz_init(z);
mpz_set_str(z, number, 10);
for (i = 0; i <= 2024; ++i) {
ret = mpz_probab_prime_p(z, REPS);
if (ret == 2) {
mpz_out_str(stdout, 10, z);
printf(" is prime number.\n");
} else if (ret == 1) {
mpz_out_str(stdout, 10, z);
printf(" may be prime number.\n");
}
mpz_add_ui(z, z, 1UL);
}
mpz_clear(z);
return 0;
}このプログラムを動かすと、以下の出力となります。
813258173412030282336987547007 may be prime number.
813258173412030282336987549031 may be prime number.813258173412030282336987547007 が擬素数と判定されました。その後に2023個の合成数があります（出力はしていない）。その後の 813258173412030282336987547031 が擬素数と判定されました。
最後に
擬素数という制限で、大きな数でも素数判定ができるプログラムを作りました。
今年も、いろいろプログラムを書いて、計算しようと考えています。
