必ず結果が素数となる公式を見つけることは多くの数学者の夢だそうですが、そのような公式は未だに見つかっていないそうです。とはいえ、これまでいくつかかなりの確率で素数を生成する公式が見つかっていますので、どれくらいの精度で見つけられるのか、検証します。まずは比較するため、奇数はどれくらい素数かを調べます。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int isprime( unsigned long long n );
int main( int ac, char *av[] )
{
unsigned long long n, n2, min_n, max_n, i;
/* コマンドラインから素数探索範囲を決定する */
if( ac < 3 )
return;
min_n = strtouq( av[1], NULL, 10 );
max_n = strtouq( av[2], NULL, 10 );
/* 探索範囲の数を調べる */
for( n = min_n; n <= max_n; n++ ) {
/* 2n + 1 を求める */
n2 = 2 * n + 1;
/* 素数かどうか調べる */
if( isprime( n2 ) )
printf( "%qu %qu OK\n", n, n2 );
else
printf( "%qu %qu NG\n", n, n2 );
}
}
int isprime( unsigned long long n )
{
unsigned long long i, n2, pn2;
/* 1は素数ではない */
if( n == 1 )
return( 0 );
/* 2以外で2で割り切れたら合成数 */
if( n != 2 && n % 2 == 0 )
return( 0 );
/* sqrt(n)以上の出来るだけ小さい値を求める */
pn2 = n2 = n;
while( n2 * n2 > n || n2 * n2 < n2 ) {
pn2 = n2;
n2 /= 2;
}
if( pn2 >= n )
n2 = n - 1;
else
n2 = pn2;
/* n2以下の奇数での剰余が0かどうか調べる */
for( i = 3; i <= n2; i += 2 ) {
if( n % i == 0 )
return( 0 );
}
/* 素数であった */
return( 1 );
}
オイラーが発見したn2+n+41は完全ではないもののかなり良い成績をあげていると言う事です。実際のところはどうでしょうか。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int isprime( unsigned long long n );
int main( int ac, char *av[] )
{
unsigned long long n, n2, min_n, max_n, i;
/* コマンドラインから素数探索範囲を決定する */
if( ac < 3 )
return;
min_n = strtouq( av[1], NULL, 10 );
max_n = strtouq( av[2], NULL, 10 );
/* 探索範囲の数を調べる */
for( n = min_n; n <= max_n; n++ ) {
/* n^2 + n + 41 を求める */
n2 = n * n + n + 41;
/* 素数かどうか調べる */
if( isprime( n2 ) )
printf( "%qu %qu OK\n", n, n2 );
else
printf( "%qu %qu NG\n", n, n2 );
}
}
int isprime( unsigned long long n )
{
unsigned long long i, n2, pn2;
/* 1は素数ではない */
if( n == 1 )
return( 0 );
/* 2以外で2で割り切れたら合成数 */
if( n != 2 && n % 2 == 0 )
return( 0 );
/* sqrt(n)以上の出来るだけ小さい値を求める */
pn2 = n2 = n;
while( n2 * n2 > n || n2 * n2 < n2 ) {
pn2 = n2;
n2 /= 2;
}
if( pn2 >= n )
n2 = n - 1;
else
n2 = pn2;
/* n2以下の奇数での剰余が0かどうか調べる */
for( i = 3; i <= n2; i += 2 ) {
if( n % i == 0 )
return( 0 );
}
/* 素数であった */
return( 1 );
}
その他に、このような式も素数を生成するとして知られているそうです。次節も同様です。
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int isprime( unsigned long long n );
int main( int ac, char *av[] )
{
unsigned long long n, n2, min_n, max_n, i;
/* コマンドラインから素数探索範囲を決定する */
if( ac < 3 )
return;
min_n = strtouq( av[1], NULL, 10 );
max_n = strtouq( av[2], NULL, 10 );
/* 探索範囲の数を調べる */
for( n = min_n; n <= max_n; n++ ) {
/* 4 * n^2 + 170 * n + 1847 を求める */
n2 = 4 * n * n + 170 * n + 1847;
/* 素数かどうか調べる */
if( isprime( n2 ) )
printf( "%qu %qu OK\n", n, n2 );
else
printf( "%qu %qu NG\n", n, n2 );
}
}
int isprime( unsigned long long n )
{
unsigned long long i, n2, pn2;
/* 1は素数ではない */
if( n == 1 )
return( 0 );
/* 2以外で2で割り切れたら合成数 */
if( n != 2 && n % 2 == 0 )
return( 0 );
/* sqrt(n)以上の出来るだけ小さい値を求める */
pn2 = n2 = n;
while( n2 * n2 > n || n2 * n2 < n2 ) {
pn2 = n2;
n2 /= 2;
}
if( pn2 >= n )
n2 = n - 1;
else
n2 = pn2;
/* n2以下の奇数での剰余が0かどうか調べる */
for( i = 3; i <= n2; i += 2 ) {
if( n % i == 0 )
return( 0 );
}
/* 素数であった */
return( 1 );
}
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
int isprime( unsigned long long n );
int main( int ac, char *av[] )
{
unsigned long long n, n2, min_n, max_n, i;
/* コマンドラインから素数探索範囲を決定する */
if( ac < 3 )
return;
min_n = strtouq( av[1], NULL, 10 );
max_n = strtouq( av[2], NULL, 10 );
/* 探索範囲の数を調べる */
for( n = min_n; n <= max_n; n++ ) {
/* 4 * n^2 + 4 * n + 59 を求める */
n2 = 4 * n * n + 4 * n + 59;
/* 素数かどうか調べる */
if( isprime( n2 ) )
printf( "%qu %qu OK\n", n, n2 );
else
printf( "%qu %qu NG\n", n, n2 );
}
}
int isprime( unsigned long long n )
{
unsigned long long i, n2, pn2;
/* 1は素数ではない */
if( n == 1 )
return( 0 );
/* 2以外で2で割り切れたら合成数 */
if( n != 2 && n % 2 == 0 )
return( 0 );
/* sqrt(n)以上の出来るだけ小さい値を求める */
pn2 = n2 = n;
while( n2 * n2 > n || n2 * n2 < n2 ) {
pn2 = n2;
n2 /= 2;
}
if( pn2 >= n )
n2 = n - 1;
else
n2 = pn2;
/* n2以下の奇数での剰余が0かどうか調べる */
for( i = 3; i <= n2; i += 2 ) {
if( n % i == 0 )
return( 0 );
}
/* 素数であった */
return( 1 );
}
実際に100万以下のnに対して調べてみた所、以下の結果になりました。
| 式 | 2n+1 | n2+n+41 | 4n2+170n+1847 | 4n2+4n+59 | |
|---|---|---|---|---|---|
| nに対する素数の存在 | 10以下 | 7個 (63.6%) | 11個 (100.0%) | 9個 (81.8%) | 11個 (100.0%) |
| 100以下 | 45個 (44.5%) | 87個 (86.1%) | 71個 (70.2%) | 72個 (71.2%) | |
| 1,000以下 | 302個 (30.1%) | 582個 (58.1%) | 509個 (50.8%) | 460個 (45.9%) | |
| 1万以下 | 2,261個 (22.6%) | 4,149個 (41.4%) | 3,822個 (38.2%) | 3,408個 (34.0%) | |
| 10万以下 | 17,983個 (17.9%) | 31,985個 (31.9%) | 29,906個 (29.9%) | 26,656個 (26.6%) | |
| 100万以下 | 148,932個 (14.8%) | 261,081個 (26.1%) | 247,425個 (24.7%) | 220,611個 (22.0%) | |
| 式 | 2n+1 | n2+n+41 | 4n2+170n+1847 | 4n2+4n+59 | |
|---|---|---|---|---|---|
| 式の値に対する素数の存在 | 10以下 | 3個 (60.0%) | - | - | - |
| 100以下 | 24個 (48.0%) | 8個 (100.0%) | - | 3個 (100.0%) | |
| 1,000以下 | 167個 (33.4%) | 31個 (100.0%) | - | 14個 (93.3%) | |
| 1万以下 | 1,228個 (24.5%) | 86個 (86.0%) | 23個 (79.3%) | 41個 (82.0%) | |
| 10万以下 | 9,591個 (19.1%) | 221個 (69.9%) | 90個 (65.6%) | 102個 (64.5%) | |
| 100万以下 | 78,497個 (15.6%) | 581個 (58.1%) | 270個 (56.3%) | 259個 (51.8%) | |
| 1000万以下 | - | 1,503個 (47.5%) | 727個 (46.6%) | 691個 (43.7%) | |
| 1億以下 | - | 4,149個 (41.4%) | 2,064個 (41.4%) | 1,843個 (36.8%) | |
| 10億以下 | - | 11,355個 (35.9%) | 5,706個 (36.1%) | 5,073個 (32.0%) | |
| 100億以下 | - | 31,985個 (31.9%) | 15,971個 (31.9%) | 14,288個 (28.5%) | |
| 1000億以下 | - | 90,940個 (28.7%) | 45,418個 (28.7%) | 40,478個 (25.6%) | |
| 1兆以下 | - | 261,081個 (26.1%) | 130,423個 (26.0%) | 116,545個 (23.3%) | |
まず奇数の場合の結果ですが、これは素数の存在確率そのものを表していることになります。nの値の結果から見ると好成績のようですが、これは式の値自体が他の式に比べると小さいですから直接比較する事は出来ません。素数は小さな数の範囲では存在確率が大きくなることが知られていますから。
他の三つの式はなかなか高い確率で素数を生成していることが分かります。奇数での素数の存在確率が15%程度になってしまう100万以下の範囲でも50%以上の結果で素数を生成しています。また、式の値が1兆以下でも25%程度の結果が素数となっていますから、これは驚異的と言ってもいいでしょう。
ちなみにそれぞれの式に当てはめるnの内、最初から連続してどこまで素数を生成し続けたかを比べてみます。まず2n+1の場合は式の値が0でいきなり素数ではありません。しかしこれは例外として除くと、n=3の場合の7までとなります。次にオイラーのn2+n+41では、n=39の場合の1601までが素数となります。4n2+170n+1847では、n=1でいきなり合成数となってしまうため、n=0の場合の1847までとなります。4n2+4n+59では、n=13の場合の787までが連続して素数となります。
こうしてみると、以上の4式の中ではオイラーの見つけたn2+n+41が僅差で最も優秀な素数生成式と言えるのではないでしょうか。