さて、Cのことは忘れてください。私があなたに番号を与えて、それが素数であるかどうかを判断するように頼んだとしましょう。どうしますか？手順を明確に書き留めてから、それらをコードに変換することを心配してください。
アルゴリズムを決定すると、プログラムの書き方を理解したり、他の人がそれを手伝ったりするのがはるかに簡単になります。
編集：投稿したC＃コードは次のとおりです。
static bool IsPrime(int number) {
for (int i = 2; i < number; i++) {
if (number % i == 0 && i != number) return false;
}
return true;
}
これは、そのままではほぼ有効なCです。boolCにはタイプがなく、またはもありません。trueそのfalseため、少し変更する必要があります（編集：Kristopher Johnsonは、C99がstdbool.hヘッダーを追加したことを正しく指摘しています）。一部の人はC99環境にアクセスできないので（ただし、C99環境を使用する必要があります！）、その非常に小さな変更を加えましょう。
int IsPrime(int number) {
int i;
for (i=2; i<number; i++) {
if (number % i == 0 && i != number) return 0;
}
return 1;
}
これはあなたが望むことをする完全に有効なCプログラムです。手間をかけずに少し改善できます。まず、それiは常により小さいことに注意しnumberてください。したがって、チェックはi != number常に成功します。私たちはそれを取り除くことができます。
また、実際に除数を試す必要はありませんnumber - 1。sqrt（number）に到達したら、チェックを停止できます。sqrtは浮動小数点演算であり、微妙な点が山積みになっているため、実際には計算しませんsqrt(number)。代わりに、次のことを確認できますi*i <= number。
int IsPrime(int number) {
int i;
for (i=2; i*i<=number; i++) {
if (number % i == 0) return 0;
}
return 1;
}
ただし、最後にもう1つ。元のアルゴリズムに小さなバグがありました！numberが負、ゼロ、または1の場合、この関数はその数が素数であると主張します。あなたはそれを適切に処理したいと思うかもしれません、そしてあなたはnumber正の値だけを気にする可能性が高いので、署名されていないようにしたいかもしれません：
int IsPrime(unsigned int number) {
if (number <= 1) return 0; // zero and one are not prime
unsigned int i;
for (i=2; i*i<=number; i++) {
if (number % i == 0) return 0;
}
return 1;
}
これは、数値が素数であるかどうかを確認するための最速の方法ではありませんが、機能し、非常に簡単です。コードを変更する必要はほとんどありませんでした。
誰もこれについて言及していないことに私は驚いています。
エラトステネスのふるいを使用する
詳細：
エラトステネスのふるいは素数を見つけて保存します。新しい数の素数がチェックされると、以前のすべての素数が既知の素数リストと照合されます。
理由：
スティーブンキャノンはそれにとてもよく答えました！
だが
これは、√nまでのすべてのmをテストする場合の3倍の速度です。
int IsPrime(unsigned int number) {
if (number <= 3 && number > 1)
return 1; // as 2 and 3 are prime
else if (number%2==0 || number%3==0)
return 0; // check if number is divisible by 2 or 3
else {
unsigned int i;
for (i=5; i*i<=number; i+=6) {
if (number % i == 0 || number%(i + 2) == 0)
return 0;
}
return 1;
}
}
このプログラムは、素数性チェックのために単一の数値をチェックするのに非常に効率的です。
bool check(int n){
if (n <= 3) {
return n > 1;
}
if (n % 2 == 0 || n % 3 == 0) {
return false;
}
int sq=sqrt(n); //include math.h or use i*i<n in for loop
for (int i = 5; i<=sq; i += 6) {
if (n % i == 0 || n % (i + 2) == 0) {
return false;
}
}
return true;
}
2からチェックしている数値のルートまでの各整数のモジュラスをチェックします。
係数がゼロに等しい場合、それは素数ではありません。
擬似コード：
bool IsPrime(int target)
{
for (i = 2; i <= root(target); i++)
{
if ((target mod i) == 0)
{
return false;
}
}
return true;
}
この質問を読んだ後、2 * 3=6の倍数でループを実行することによって最適化を提供する回答があるという事実に興味をそそられました。
そこで、同じアイデアで、2 * 3 * 5=30の倍数で新しい関数を作成します。
int check235(unsigned long n)
{
unsigned long sq, i;
if(n<=3||n==5)
return n>1;
if(n%2==0 || n%3==0 || n%5==0)
return 0;
if(n<=30)
return checkprime(n); /* use another simplified function */
sq=ceil(sqrt(n));
for(i=7; i<=sq; i+=30)
if (n%i==0 || n%(i+4)==0 || n%(i+6)==0 || n%(i+10)==0 || n%(i+12)==0
|| n%(i+16)==0 || n%(i+22)==0 || n%(i+24)==0)
return 0;
return 1;
}
両方の関数を実行し、時間をチェックすることで、この関数の方が本当に高速であると言えます。2つの異なる素数を使用した2つのテストを見てみましょう。
$ time ./testprimebool.x 18446744069414584321 0
f(2,3)
Yes, its prime.
real 0m14.090s
user 0m14.096s
sys 0m0.000s
$ time ./testprimebool.x 18446744069414584321 1
f(2,3,5)
Yes, its prime.
real 0m9.961s
user 0m9.964s
sys 0m0.000s
$ time ./testprimebool.x 18446744065119617029 0
f(2,3)
Yes, its prime.
real 0m13.990s
user 0m13.996s
sys 0m0.004s
$ time ./testprimebool.x 18446744065119617029 1
f(2,3,5)
Yes, its prime.
real 0m10.077s
user 0m10.068s
sys 0m0.004s
だから私は、一般化した場合、誰かがあまりにも多くを得るだろうかと思いました。私は、最初に包囲を行って素数階乗素の特定のリストをクリーンアップし、次にこのリストを使用して大きい方の素数を計算する関数を思いつきました。
int checkn(unsigned long n, unsigned long *p, unsigned long t)
{
unsigned long sq, i, j, qt=1, rt=0;
unsigned long *q, *r;
if(n<2)
return 0;
for(i=0; i<t; i++)
{
if(n%p[i]==0)
return 0;
qt*=p[i];
}
qt--;
if(n<=qt)
return checkprime(n); /* use another simplified function */
if((q=calloc(qt, sizeof(unsigned long)))==NULL)
{
perror("q=calloc()");
exit(1);
}
for(i=0; i<t; i++)
for(j=p[i]-2; j<qt; j+=p[i])
q[j]=1;
for(j=0; j<qt; j++)
if(q[j])
rt++;
rt=qt-rt;
if((r=malloc(sizeof(unsigned long)*rt))==NULL)
{
perror("r=malloc()");
exit(1);
}
i=0;
for(j=0; j<qt; j++)
if(!q[j])
r[i++]=j+1;
free(q);
sq=ceil(sqrt(n));
for(i=1; i<=sq; i+=qt+1)
{
if(i!=1 && n%i==0)
return 0;
for(j=0; j<rt; j++)
if(n%(i+r[j])==0)
return 0;
}
return 1;
}
コードを最適化しなかったと思いますが、それは公平です。さて、テスト。非常に多くの動的メモリがあるため、リスト235はハードコードされた235よりも少し遅いと予想しました。しかし、あなたが以下を見ることができるように、それは大丈夫でした。その後、時間はどんどん小さくなり、最高のリストは次のようになりました。
2 3 5 7 11 13 17 19
8.6秒で。したがって、誰かがそのような手法を利用するハードコードされたプログラムを作成する場合は、ゲインがそれほど大きくないため、リスト23および5を使用することをお勧めします。しかしまた、コーディングする気があるなら、このリストは大丈夫です。問題は、ループなしですべてのケースを述べることができないか、コードが非常に大きくなることです（1658879がありORs、||それぞれの内部にありますif）。次のリスト：
2 3 5 7 11 13 17 19 23
時間は13秒で大きくなり始めました。ここに全体のテストがあります：
$ time ./testprimebool.x 18446744065119617029 2 3 5
f(2,3,5)
Yes, its prime.
real 0m12.668s
user 0m12.680s
sys 0m0.000s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7
f(2,3,5,7)
Yes, its prime.
real 0m10.889s
user 0m10.900s
sys 0m0.000s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11
f(2,3,5,7,11)
Yes, its prime.
real 0m10.021s
user 0m10.028s
sys 0m0.000s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13
f(2,3,5,7,11,13)
Yes, its prime.
real 0m9.351s
user 0m9.356s
sys 0m0.004s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17
f(2,3,5,7,11,13,17)
Yes, its prime.
real 0m8.802s
user 0m8.800s
sys 0m0.008s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19
f(2,3,5,7,11,13,17,19)
Yes, its prime.
real 0m8.614s
user 0m8.564s
sys 0m0.052s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19 23
f(2,3,5,7,11,13,17,19,23)
Yes, its prime.
real 0m13.013s
user 0m12.520s
sys 0m0.504s
$ time ./testprimebool.x 18446744065119617029 2 3 5 7 11 13 17 19 23 29
f(2,3,5,7,11,13,17,19,23,29)
q=calloc(): Cannot allocate memory
PS。私は意図的に解放しませんでした。プログラムが終了するとすぐにメモリが解放されるため、このタスクをOSに与えて、時間を稼ぎました。ただし、計算後にコードを実行し続ける場合は、解放することをお勧めします。
ボーナス
int check2357(unsigned long n)
{
unsigned long sq, i;
if(n<=3||n==5||n==7)
return n>1;
if(n%2==0 || n%3==0 || n%5==0 || n%7==0)
return 0;
if(n<=210)
return checkprime(n); /* use another simplified function */
sq=ceil(sqrt(n));
for(i=11; i<=sq; i+=210)
{
if(n%i==0 || n%(i+2)==0 || n%(i+6)==0 || n%(i+8)==0 || n%(i+12)==0 ||
n%(i+18)==0 || n%(i+20)==0 || n%(i+26)==0 || n%(i+30)==0 || n%(i+32)==0 ||
n%(i+36)==0 || n%(i+42)==0 || n%(i+48)==0 || n%(i+50)==0 || n%(i+56)==0 ||
n%(i+60)==0 || n%(i+62)==0 || n%(i+68)==0 || n%(i+72)==0 || n%(i+78)==0 ||
n%(i+86)==0 || n%(i+90)==0 || n%(i+92)==0 || n%(i+96)==0 || n%(i+98)==0 ||
n%(i+102)==0 || n%(i+110)==0 || n%(i+116)==0 || n%(i+120)==0 || n%(i+126)==0 ||
n%(i+128)==0 || n%(i+132)==0 || n%(i+138)==0 || n%(i+140)==0 || n%(i+146)==0 ||
n%(i+152)==0 || n%(i+156)==0 || n%(i+158)==0 || n%(i+162)==0 || n%(i+168)==0 ||
n%(i+170)==0 || n%(i+176)==0 || n%(i+180)==0 || n%(i+182)==0 || n%(i+186)==0 ||
n%(i+188)==0 || n%(i+198)==0)
return 0;
}
return 1;
}
時間：
$ time ./testprimebool.x 18446744065119617029 7
h(2,3,5,7)
Yes, its prime.
real 0m9.123s
user 0m9.132s
sys 0m0.000s
偶数（2小節）が素数になることはできないことを付け加えておきます。これにより、forループの前に別の条件が発生します。したがって、終了コードは次のようになります。
int IsPrime(unsigned int number) {
if (number <= 1) return 0; // zero and one are not prime
if ((number > 2) && ((number % 2) == 0)) return 0; //no even number is prime number (bar 2)
unsigned int i;
for (i=2; i*i<=number; i++) {
if (number % i == 0) return 0;
}
return 1;
}
int is_prime(int val)
{
int div,square;
if (val==2) return TRUE; /* 2 is prime */
if ((val&1)==0) return FALSE; /* any other even number is not */
div=3;
square=9; /* 3*3 */
while (square<val)
{
if (val % div == 0) return FALSE; /* evenly divisible */
div+=2;
square=div*div;
}
if (square==val) return FALSE;
return TRUE;
}
2と偶数の処理は、奇数を奇数で割ったものだけを処理するメインループから除外されます。これは、偶数を法とする奇数は常にゼロ以外の答えを与えるため、これらのテストは冗長になるためです。または、言い換えると、奇数は別の奇数で均等に割り切れるが、偶数では割り切れない場合があります（E * E => E、E * O => E、O * E => E、およびO * O => O）。
除算/モジュラスは、x86アーキテクチャでは実際にコストがかかりますが、コストはさまざまです（http://gmplib.org/~tege/x86-timing.pdfを参照）。一方、掛け算はかなり安いです。
オーバーフローバグを回避する
unsigned i, number;
...
for (i=2; i*i<=number; i++) { // Buggy
for (i=2; i*i<=number; i += 2) { // Buggy
// or
for (i=5; i*i<=number; i+=6) { // Buggy
numberが素数でi*iあり、型の最大値に近い場合、これらの形式は正しくありません。
問題はすべての整数型、signed, unsignedおよびそれ以上に存在します。
例：
最大整数UINT_MAX_SQRT値の平方根の床とします。たとえば、unsignedが32ビットの場合は65535です。
の場合、このfor (i=2; i*i<=number; i++)10年前の失敗は、UINT_MAX_SQRT*UINT_MAX_SQRT <= numberとnumberが素数の場合、次の反復で乗算オーバーフローが発生するために発生します。タイプが符号付きタイプの場合、オーバーフローはUBです。符号なしタイプの場合、これ自体はUBではありませんが、ロジックは機能していません。切り捨てられた積がを超えるまで、対話は続行されますnumber。誤った結果が発生する可能性があります。32ビットunsignedの場合、プライムである4,294,967,291を試してください。
メルセンヌ素数some_integer_type_MAXだった場合、決して真実ではありません。i*i<=number
このバグを回避するには、商と剰余の計算が一緒に行われるため、多くのコンパイラでが効率的であると考えてくださいnumber%i。number/iしたがって、両方を実行するための追加コストは発生しません。
シンプルなフルレンジソリューション：
bool IsPrime(unsigned number) {
for(unsigned i = 2; i <= number/i; i++){
if(number % i == 0){
return false;
}
}
return number >= 2;
}
エラトステネスのふるいを使用すると、「既知の幅の」素数アルゴリズムと比較して、計算が非常に高速になります。
wiki（https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes）の擬似コードを使用することで、C＃で解決策を得ることができます。
public bool IsPrimeNumber(int val) {
// Using Sieve of Eratosthenes.
if (val < 2)
{
return false;
}
// Reserve place for val + 1 and set with true.
var mark = new bool[val + 1];
for(var i = 2; i <= val; i++)
{
mark[i] = true;
}
// Iterate from 2 ... sqrt(val).
for (var i = 2; i <= Math.Sqrt(val); i++)
{
if (mark[i])
{
// Cross out every i-th number in the places after i (all the multiples of i).
for (var j = (i * i); j <= val; j += i)
{
mark[j] = false;
}
}
}
return mark[val];
}
IsPrimeNumber（1000000000）は21秒758ミリ秒かかります。
注：値はハードウェアの仕様によって異なる場合があります。