C – 确定一个数是否为素数

我试图想出一个方法,需要一个整数,并返回一个布尔值来说,如果数是质数或不,我不知道多lessC; 谁会照顾给我一些指针?

基本上,我会这样做在C#中是这样的:

static bool IsPrime(int number) { for (int i = 2; i < number; i++) { if (number % i == 0 && i != number) return false; } return true; } 

好,那就忘了C.假设我给你一个号码,并要求你确定它是否是素数。 你怎么做呢? 清楚地写下步骤, 然后担心将它们翻译成代码。

一旦你确定了algorithm,你将更容易找出如何编写一个程序,并为其他人来帮助你。

编辑:这是您发布的C#代码:

 static bool IsPrime(int number) { for (int i = 2; i < number; i++) { if (number % i == 0 && i != number) return false; } return true; } 

这是非常接近有效的C; C中没有booltypes,也没有true或者false ,所以你需要稍微修改它(编辑:Kristopher Johnson正确地指出C99增加了stdbool.h头文件)。 由于有些人不能访问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总是less于number ,所以检查i != number总是成功; 我们可以摆脱它。

另外,你实际上并不需要一直尝试除数到number - 1 ; 你可以停止检查何时达到sqrt(数字)。 由于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; } 

最后一件事, 原来的algorithm有一个小错误! 如果number是负数,或者是零,或者是一个,那么这个函数会声称这个数字是素数。 您可能想要正确处理这个问题,并且您可能希望将number作为无符号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; } 

这绝对不是检查数字是否为素数的最快方法,但是它是有效的,而且非常简单。 我们几乎不得不修改你的代码!

我很惊讶,没有人提到这一点。

使用Eratosthenes的筛子

细节:

  1. 除了1和他们自己之外,基本上非数字可以被另一个数字整除
  2. 因此:一个非顶数将是素数的乘积。

Eratosthenes的筛子find一个素数并存储它。 当一个新的数字被检查的时候,所有以前的素数都是根据已知的素数列表进行检查的。

原因:

  1. 这个algorithm/​​问题被称为“ 令人尴尬的并行 ”
  2. 它创build一个素数的集合
  3. 它是一个dynamic编程问题的例子
  4. 它快!

斯蒂芬·佳能回答得非常好!

  • 通过观察所有质数的forms为6k±1,algorithm可以进一步改进,除了2和3。
  • 这是因为对于某个整数k和对于i = -1,0,1,2,3或4,所有整数可以表示为(6k + i) 2分(6k + 0),(6k + 2),(6k + 4); 和3分(6k + 3)。
  • 所以更有效的方法是检验n是否可以被2或3整除,然后检查forms6k±1≤√n的所有数字。
  • 这是testing所有m达到√n的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; } } 
  1. build立一个小素数表,并检查他们是否分割你的input数字。
  2. 如果这个数字能够存活到1,那么尝试增加基础的伪素性testing。 例如,见Miller-Rabin素性testing 。
  3. 如果你的数量能够存活到2,那么你可以得出结论,如果它低于一些众所周知的范围,那么它就是最好的。 否则,你的答案只会是“可能素数”。 你会在维基页面find这些边界的一些值。

检查从2到您正在检查的数字的根的每个整数的模数。

如果模数等于零,那么它不是素数。

伪代码:

 bool IsPrime(int target) { for (i = 2; i <= root(target); i++) { if ((target mod i) == 0) { return false; } } return true; } 

这个程序是非常有效的检查一个单一的数字素质检查。

 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栏)可以是质数。 这导致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; } 

读完这个问题之后,我对一些答案通过运行2 * 3 = 6倍数的循环提供了优化的事实感到兴趣。

所以我用同样的想法创build一个新的函数,但是有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个不同素数的testing:

 $ 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; } 

我假设我没有优化代码,但这是公平的。 现在,testing。 因为这么多的dynamic内存,我预计列表2 3 5比2 3 5硬编码慢一点。 但是,你可以看到下面的情况。 之后,时间越来越less,最终的榜单是:

2 3 5 7 11 13 17 19

8.6秒。 所以,如果有人会创build一个使用这种技术的硬编码程序,我会build议使用列表2 3和5,因为增益不是那么大。 而且,如果愿意编码,这个列表是好的。 问题是你不能说没有循环的所有情况下,或者你的代码将是非常大的(将有1658879 ORs ,这是||在各自的内部if )。 下一个列表:

2 3 5 7 11 13 17 19 23

时间开始变得更大,13秒。 这里整个testing:

 $ 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。 我并没有有意识地将这个任务交给操作系统,因为一旦程序退出,内存就会被释放,以获得一些时间。 但是如果打算在计算之后继续运行代码,则释放它是明智的。


奖金

 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 
 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和偶数的处理不在主循环中,只处理奇数除以奇数。 这是因为奇数模偶数总是给出一个非零的答案,这使得这些testing是多余的。 或者,换句话说,奇数可以被另一个奇数整除,但是从不偶数(E * E => E,E * O => E,O * E => E和O * O => O)。

x86架构上的部门/模块成本非常高昂,但成本有多大(参见http://gmplib.org/~tege/x86-timing.pdf )。 另一方面,乘法相当便宜。

使用Eratosthenes的Sieve,与“已知的”素数algorithm相比,计算速度相当快。

通过使用wiki中的伪代码( https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes ),我可以在C#上获得解决scheme。

 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)需要21s 758ms。

注意 :值可能会根据硬件规格而有所不同。