素数判定アルゴリズムの実現
4178 ワード
1.素数判定問題
素数判定問題は非常によく見られる問題であり,本稿ではよく用いられるいくつかの判定方法を紹介した.
2.元のアルゴリズム
素数の定義は、1とそれ自体で除去でき、他の任意の数で除去できない数を除く.素数定義によればnを2〜n−1で除去するだけであり、いずれも除去できない場合、nは素数であり、そうでなければ、そのうちの1つの数が除去できる限り、nは素数ではない.
3.アルゴリズムの改善
nが素数でなければ、nはa*bと表すことができ、そのうち2<=a<=b<=n-1であれば、a,bの中に必ず1つの数が満たされる:1
4.フィルタアルゴリズム
より効率的な素数判断方法は、素数を予め1つの素数テーブルに保存し、1つの数が素数であるか否かを判断した場合に、直接テーブルを調べることである.この方法は2つの問題を解決する必要があります.
(1)素数表の入手方法(フィルタリング方法を採用する)(2)素数テーブルのサイズをどのように減らすか.(ビットマップデータ構造を採用)
1からnまでのすべての整数について,それらが素数であるか否かを1つずつ判断し,非素数を見つけて掘り下げ,最後に残ったのが素数である.具体的な方法は次のとおりです.
<1>is_の定義primer[i] = true; <2>2から順にis全体を巡るprimer(sqrt(N)まで)、is_primer[i]=trueの場合、is_primer[n*i]=false例えば1,2,3,4,5,6,7,8,9,10であれば、2から遍歴:is_primer[2]=trueの場合、is_primer[4]= is_primer[6]= is_primer[8]= is_primer[10]= true is_primer[3]=trueの場合、is_primer[6]= is_primer[9]=trueメモリ使用率を低減するため、アルゴリズムはビットマップデータ構造を用いる、ビットマップについては//www.jb 51を参照することができる.net/article/54439.htm
5.最適化されたフィルタリングアルゴリズム
(1)記憶方式の最適化
依然としてビットマップ方式で記憶されているが、ビットマップに奇数しか記憶されていないため、一気に半分の空間(必要な空間は4 G/(32*2)=64 MB)を節約した記憶空間最適化後、アルゴリズム効率も大幅に向上する.例えば、1,2,...,30は3,5,7,9,11,13,17,19,21,23,25,27 i=0,is_primer[0]=true、下付き[3][6][9][12]、すなわち9,15,21,27、false i=1,s_primer[0]=true、下を[6][11]、すなわち15,25をfalse i=2、2*i+3>sqrt(30)、終了:i=s、下をs(2*t+1)+3 tと表記し、そのうち、t=1,2,3,...のすべてのis_primerをfalseに設定
(2)最適化削除アルゴリズム
aは素数で、次の起点はa*aで、後ろのすべてのa*a+2*i*aをふるい落とす.すなわちn以内の素数を求めるには,まずsqrt(n)内の素数を求め,求めた素数で後の合数をふるい出す.
6.まとめ
これまで、素数の分布法則を発見した人は誰もいなかったし、1つの公式ですべての素数を計算できる人もいなかった.素数のたくさんの面白い性質あるいは科学者の努力について、例えば:
(1)Gaussは,n内の素数個数がn/ln(n)に相当するか,あるいはnが大きい場合,両者の桁は同じであると推測した.これが有名な素数の定理です.
(2)17世紀のフェルマの推測では,2の2^n次方+1,n=0,1,2...は素数であり,この数をフェルマ素数と呼ぶが,残念ながらn=5の場合,2^32+1は素数ではなく,今まで6番目のフェルマ素数は見つからなかった.
(3)18世紀に発見された最大素数は2^31-1であり、19世紀に発見された最大素数は2^127-1であり、20世紀末に人類で知られた最大素数は2^859433-1であり、10進数で表され、258715桁の数字である.
(4)双晶素数推定:差が2の素数は無限に多い.現在知られている最大の双晶素数は1159142985です×2^2304-1と1159142985×2^2304＋1.
(5)ゴッドバッハは,2より大きいすべての偶数は2つの素数の和であり,5より大きいすべての奇数は3つの素数の和であると推測した.その中で2番目の推測は1番目の自然推論であるため、ゴッドバッハ推測は1+1問題とも呼ばれている.わが国の数学者陳景潤は1+2を証明した.すなわち、2より大きい偶数はすべて1つの素数と2つの素数因数しかない合数の和である.国際的に陳氏の定理と呼ばれている.
素数判定問題は非常によく見られる問題であり,本稿ではよく用いられるいくつかの判定方法を紹介した.
2.元のアルゴリズム
素数の定義は、1とそれ自体で除去でき、他の任意の数で除去できない数を除く.素数定義によればnを2〜n−1で除去するだけであり、いずれも除去できない場合、nは素数であり、そうでなければ、そのうちの1つの数が除去できる限り、nは素数ではない.
bool is_primer1(int num) {
int i;
for(i = 2; i < num; i++) {
if(num % i == 0) {
return true;
}
}
return false;
}
3.アルゴリズムの改善
nが素数でなければ、nはa*bと表すことができ、そのうち2<=a<=b<=n-1であれば、a,bの中に必ず1つの数が満たされる:1
bool is_primer2(int num) {
int i;
int upper = sqrt(num);
printf("primer2:%d
", upper);
for(i = 2; i <= upper; i++) {
if(num % i == 0) {
return true;
}
}
return false;
}
4.フィルタアルゴリズム
より効率的な素数判断方法は、素数を予め1つの素数テーブルに保存し、1つの数が素数であるか否かを判断した場合に、直接テーブルを調べることである.この方法は2つの問題を解決する必要があります.
(1)素数表の入手方法(フィルタリング方法を採用する)(2)素数テーブルのサイズをどのように減らすか.(ビットマップデータ構造を採用)
1からnまでのすべての整数について,それらが素数であるか否かを1つずつ判断し,非素数を見つけて掘り下げ,最後に残ったのが素数である.具体的な方法は次のとおりです.
<1>is_の定義primer[i] = true; <2>2から順にis全体を巡るprimer(sqrt(N)まで)、is_primer[i]=trueの場合、is_primer[n*i]=false例えば1,2,3,4,5,6,7,8,9,10であれば、2から遍歴:is_primer[2]=trueの場合、is_primer[4]= is_primer[6]= is_primer[8]= is_primer[10]= true is_primer[3]=trueの場合、is_primer[6]= is_primer[9]=trueメモリ使用率を低減するため、アルゴリズムはビットマップデータ構造を用いる、ビットマップについては//www.jb 51を参照することができる.net/article/54439.htm
bool load_primer_table1() { //
int i;
for(i = 1; i < INT_MAX; i++) {
if(i % 2 != 0 //
&& is_primer2(i)) {
set(i);
}
}
}
bool load_primer_table2() {//
int i, j;
for(i = 1; i <= INT_MAX; i++) {
if( i % 2) {
set(i);
} else {
clear(i);
}
}
int upper = sqrt(INT_MAX);
for(i = 1; i <= upper; i++) {
if(test(i)) {
for(j = i + i; j < INT_MAX; j += i)
set(i);
}
}
}
bool is_primer3(long num) { //
if(test(num))
return true;
return false;
}
5.最適化されたフィルタリングアルゴリズム
(1)記憶方式の最適化
依然としてビットマップ方式で記憶されているが、ビットマップに奇数しか記憶されていないため、一気に半分の空間(必要な空間は4 G/(32*2)=64 MB)を節約した記憶空間最適化後、アルゴリズム効率も大幅に向上する.例えば、1,2,...,30は3,5,7,9,11,13,17,19,21,23,25,27 i=0,is_primer[0]=true、下付き[3][6][9][12]、すなわち9,15,21,27、false i=1,s_primer[0]=true、下を[6][11]、すなわち15,25をfalse i=2、2*i+3>sqrt(30)、終了:i=s、下をs(2*t+1)+3 tと表記し、そのうち、t=1,2,3,...のすべてのis_primerをfalseに設定
(2)最適化削除アルゴリズム
aは素数で、次の起点はa*aで、後ろのすべてのa*a+2*i*aをふるい落とす.すなわちn以内の素数を求めるには,まずsqrt(n)内の素数を求め,求めた素数で後の合数をふるい出す.
6.まとめ
これまで、素数の分布法則を発見した人は誰もいなかったし、1つの公式ですべての素数を計算できる人もいなかった.素数のたくさんの面白い性質あるいは科学者の努力について、例えば:
(1)Gaussは,n内の素数個数がn/ln(n)に相当するか,あるいはnが大きい場合,両者の桁は同じであると推測した.これが有名な素数の定理です.
(2)17世紀のフェルマの推測では,2の2^n次方+1,n=0,1,2...は素数であり,この数をフェルマ素数と呼ぶが,残念ながらn=5の場合,2^32+1は素数ではなく,今まで6番目のフェルマ素数は見つからなかった.
(3)18世紀に発見された最大素数は2^31-1であり、19世紀に発見された最大素数は2^127-1であり、20世紀末に人類で知られた最大素数は2^859433-1であり、10進数で表され、258715桁の数字である.
(4)双晶素数推定:差が2の素数は無限に多い.現在知られている最大の双晶素数は1159142985です×2^2304-1と1159142985×2^2304＋1.
(5)ゴッドバッハは,2より大きいすべての偶数は2つの素数の和であり,5より大きいすべての奇数は3つの素数の和であると推測した.その中で2番目の推測は1番目の自然推論であるため、ゴッドバッハ推測は1+1問題とも呼ばれている.わが国の数学者陳景潤は1+2を証明した.すなわち、2より大きい偶数はすべて1つの素数と2つの素数因数しかない合数の和である.国際的に陳氏の定理と呼ばれている.