我试图想出一个方法，它接受一个整数并返回一个布尔值来说明这个数字是否是素数，而且我不太了解 C；有人愿意给我一些指示吗？
基本上，我会在 C# 中这样做：
static bool IsPrime(int number)
{
for (int i = 2; i < number; i++)
{
if (number % i == 0 && i != number)
return false;
}
return true;
}
问问题
200464 次
11 回答
154
好的，忘掉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 语言；C 中没有bool类型，也没有trueor 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总是小于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;
}
不过，最后一件事；您的原始算法中有一个小错误！如果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;
}
这绝对不是检查一个数字是否为素数的最快方法，但它有效，而且非常简单。我们几乎不需要修改您的代码！
于 2009-10-08T15:46:48.563 回答
16
斯蒂芬佳能回答得很好！
但
- 通过观察除 2 和 3 之外的所有素数的形式为 6k ± 1，可以进一步改进该算法。
- 这是因为对于某个整数 k 和 i = -1、0、1、2、3 或 4，所有整数都可以表示为 (6k + i)；2 除 (6k + 0), (6k + 2), (6k + 4); 和 3 个除法 (6k + 3)。
- 所以一个更有效的方法是测试 n 是否能被 2 或 3 整除，然后检查 6k ± 1 ≤ √n 形式的所有数。
这是测试所有 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; } }
于 2014-11-05T14:51:04.937 回答
10
- 建立一个小素数表，并检查它们是否除以您的输入数。
- 如果数字存活到 1，请尝试增加基数的伪素数测试。例如，参见Miller-Rabin 素数检验。
- 如果您的数字存活到 2，那么如果它低于某个众所周知的界限，您可以断定它是素数。否则你的答案只会是“可能是素数”。您将在 wiki 页面中找到这些边界的一些值。
于 2009-10-08T15:52:24.730 回答
4
该程序对于检查单个数字进行素数检查非常有效。
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;
}
于 2015-04-30T22:52:17.477 回答
3
检查从 2 到您正在检查的数字的根的每个整数的模数。
如果模数为零，则它不是素数。
伪代码：
bool IsPrime(int target)
{
for (i = 2; i <= root(target); i++)
{
if ((target mod i) == 0)
{
return false;
}
}
return true;
}
于 2009-10-08T15:52:33.230 回答
3
After reading this question, I was intrigued by the fact that some answers offered optimization by running a loop with multiples of 2*3=6.
So I create a new function with the same idea, but with multiples of 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;
}
By running both functions and checking times I could state that this function is really faster. Lets see 2 tests with 2 different primes:
$ 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
So I thought, would someone gain too much if generalized? I came up with a function that will do a siege first to clean a given list of primordial primes, and then use this list to calculate the bigger one.
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;
}
I assume I did not optimize the code, but it's fair. Now, the tests. Because so many dynamic memory, I expected the list 2 3 5 to be a little slower than the 2 3 5 hard-coded. But it was ok as you can see bellow. After that, time got smaller and smaller, culminating the best list to be:
2 3 5 7 11 13 17 19
With 8.6 seconds. So if someone would create a hardcoded program that makes use of such technique I would suggest use the list 2 3 and 5, because the gain is not that big. But also, if willing to code, this list is ok. Problem is you cannot state all cases without a loop, or your code would be very big (There would be 1658879 ORs, that is || in the respective internal if). The next list:
2 3 5 7 11 13 17 19 23
time started to get bigger, with 13 seconds. Here the whole test:
$ 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. I did not free(r) intentionally, giving this task to the OS, as the memory would be freed as soon as the program exited, to gain some time. But it would be wise to free it if you intend to keep running your code after the calculation.
BONUS
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:
$ time ./testprimebool.x 18446744065119617029 7
h(2,3,5,7)
Yes, its prime.
real 0m9.123s
user 0m9.132s
sys 0m0.000s
于 2015-08-01T05:50:03.453 回答
2
我只想补充一点，没有偶数（小节 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;
}
于 2010-02-11T11:55:26.740 回答
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 => 哦）。
在 x86 架构上，除法/模数确实很昂贵，尽管成本各不相同（请参阅http://gmplib.org/~tege/x86-timing.pdf）。另一方面，乘法非常便宜。
于 2011-05-30T12:14:05.727 回答
1
避免溢出错误
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作为最大整数值的平方根的下限。例如 65535unsigned是 32 位的。
有了for (i=2; i*i<=number; i++)，这个 10 年的失败发生是因为当UINT_MAX_SQRT*UINT_MAX_SQRT <= number和number是素数时，下一次迭代会导致乘法溢出。如果类型是有符号类型，则溢出为 UB。对于unsigned types，这本身不是 UB，但逻辑已经崩溃。交互继续进行，直到截断的乘积超过number。可能会出现不正确的结果。使用 32-bit unsigned，尝试 4,294,967,291 这是一个素数。
如果some_integer_type_MAX是梅森素数，i*i<=number则永远不会是真的。
为避免此错误，请考虑 ,number%i在number/i许多编译器上是有效的，因为商和余数的计算是一起完成的，因此与仅 1 相比，两者都不会产生额外的成本。
一个简单的全方位解决方案：
bool IsPrime(unsigned number) {
for(unsigned i = 2; i <= number/i; i++){
if(number % i == 0){
return false;
}
}
return number >= 2;
}
于 2019-02-10T04:52:34.877 回答
0
使用埃拉托色尼筛法，与“已知范围”的素数算法相比，计算速度要快得多。
通过使用它的 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 毫秒。
注：值可能因硬件规格而异。
于 2016-05-12T04:04:19.573 回答