我想写一个方法，输入一个整数，返回一个布尔值，表示这个数是不是素数。我的 C 语言知识有限，请问有人能指点一下吗？
在 C# 中，我会这样实现：
static bool IsPrime(int number)
{
for (int i = 2; i < number; i++)
{
if (number % i == 0 && i != number)
return false;
}
return true;
}
12个回答
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类型，也没有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 总是小于 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是负数、零或者是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;
}
这绝对不是检查一个数是否为质数的最快方法，但它能够工作，而且非常简单明了。我们几乎没改动你的代码！
- Stephen Canon
22
12C99标准定义了一个<stdbool.h>头文件，提供了
bool、true和false。 - Kristopher Johnson29我知道计算一个平方比计算一个平方根要简单，但是在每次迭代中计算一个平方应该比计算一次平方根的成本更高 :x - Matthieu M.
6在现代乱序执行的计算机上，用于平方i的乘法指令的延迟应该完全隐藏在模数的延迟中，因此不会有明显的性能提升。在严格的顺序执行计算机上，使用提前提取的平方根可以获得优势，但如果代码编译在具有大整数类型（64位或更大）的平台上，则可能引发浮点精度问题。所有这些都可以处理，但最好保持简单和易于移植。毕竟，如果您关心速度，就根本不会使用此算法。 - Stephen Canon
5@Tom，你可以通过在floor(sqrt(number))处停止来进一步提高。以11为例，floor(sqrt(11)) = 3。 3后面的数字是4，3 * 4 = 12 > 11。如果您正在使用简单筛法来检查质数，除了2之外，只需要检查原始数的平方根以下的奇数即可。 - Calyth
显示剩余17条评论
29
- monksy
7
9这段话的意思是：如果计算只涉及单个值，那么它的空间复杂度也是O(n)，这样做没有性能上的收益，却浪费了大量空间。 - R.. GitHub STOP HELPING ICE
3实际上，如果你要支持大数字的话，时间复杂度可能会达到O(n log n)或更高。 - R.. GitHub STOP HELPING ICE
2谁会在应用程序的生命周期内仅计算一个质数值？质数是很适合被缓存的候选对象。 - monksy
2一个在查询后终止的命令行程序是一个明显的例子。无论如何，保持全局状态很丑陋，应始终考虑权衡。我甚至可以说，（在运行时生成的）筛子基本上是没用的。如果您的质数候选者足够小，以至于您可以将这样大小的筛子装入内存中，那么您应该只有一个“ static const”位图表示哪些数字是质数，并使用它，而不是在运行时填充它。 - R.. GitHub STOP HELPING ICE
1埃拉托斯特尼筛法是解决“生成所有小于n的质数”的好方法（嗯，还算不错）。但它并不适用于解决“n是质数吗？”这个问题。 - hobbs
显示剩余2条评论
18
Stephen Canon已经很好地回答了这个问题！
但是
- The algorithm can be improved further by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3.
- This is because all integers can be expressed as (6k + i) for some integer k and for i = −1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3).
- So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1 ≤ √n.
This is 3 times as fast as testing all m up to √n.
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; } }
- Blackhat002
7
3当 (number == 1) 时，你应该返回
0，因为1不是质数。 - Ahmad Ibrahim1这种优化在我看来对于这个任务是不相关的：为什么要停留在形式为 6k ± 1 除了2和3 的形式上，它重写成了 _n^2 mod 6 = 1_，而你可以有 n^4 mod 30 = 1 除了2、3、5 ...实际上，你可以一直进行下去，因为你正在使用质数来进行这种优化...而这正是更普遍的埃拉托斯特尼筛法的原则 :) - ghilesZ
2@GhilesZ：我不同意，这对问题非常相关，并且使用一个“||”可以使基本循环的运行速度提高3倍。 - verdy_p
你可以继续使用相同的技巧，通过步长为30（即235）并测试9个候选值（30k+{1;7;11;13;17;19;21;23;29}），而不使用crible数组，来使用下一个质数（5）。然而，我认为在循环中预先计算sqrt(i)一次比计算i*i乘积更快。 - verdy_p
1你会发现，在前两个质数上的第一次优化获得了很大的收益（测试2个候选项的循环少了6倍，即比所有奇数循环快3倍）。在前3个质数上的优化（测试8个候选项的循环少了30倍，即比所有奇数循环快30/8=3.75倍），但是收益不那么显著。这是普遍的情况：使用通用筛法不会显著提高速度！ - verdy_p
显示剩余2条评论
10
- 构建一个小素数表，并检查它们是否能够整除您输入的数字。
- 如果数字在第1步中存活下来，可以使用递增的基数进行伪素性测试。例如，请参考Miller-Rabin素性测试。
- 如果数字在第2步中幸存，且其值小于某些已知界限，则可以得出它是质数的结论。否则，您的答案将仅为“可能是质数”。您可以在维基页面上找到这些界限的一些值。
- Eric Bainville
2
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;
}
- GorvGoyl
3
1测试素数，应该从
i=2 到 i<=ceil(sqrt(n))。你在测试中错过了 2 个数字：首先，强制转换为 (int) 会使 sqrt(n) 截断小数部分。其次，你使用了 i<sq，而应该是 i<=sq。现在，假设存在一个符合这个问题的数字。一个合成数 n，它有 ceil(sqrt(n)) 作为较小的因子。你的内部循环运行 i 的值如下：(5, 7), (11, 13), (17, 19), (23, 25), (29, 31), (35, 37), (41, 43)，以此类推，即 n%i 和 n%(i+2)。假设我们得到 sqrt(1763)=41.98。由于 1763=41*43 是一个合成数，你的循环只会运行到 (35, 37) 并失败。 - DrBeco@DrBeco 很好的观察！感谢提供示例。已更新代码。 - GorvGoyl
3经过仔细分析
ceil() 的问题，我意识到尽管许多网站推荐使用它，但这只是画蛇添足。你可以使用 i<=sqrt(n) 进行截取和测试，就可以了。测试案例是在质数之间极大的。例如：86028221*86028223=7400854980481283，而 sqrt(7400854980481283)~86028222。而更小的两个质数 2 和 3，会得出 sqrt(6)=2.449，截取后还是留下了 2。（但更小的数字不是测试案例，只是作为比较来说明一个观点）。所以，现在算法是正确的了，没有必要使用 ceil()。 - DrBeco3
阅读完这个问题后，我被一些答案提供了通过运行一个乘以2*3=6的循环进行优化的事实所吸引。
因此，我创建了一个新函数，但是使用的是2*3*5=30的倍数。
通过运行两个函数并检查时间，我可以声明这个函数确实更快。让我们看看两个不同的质数进行的2个测试：
我想我没有对代码进行优化，但还算公平。现在是测试阶段。由于有很多动态内存，我预计2 3 5列表会比硬编码的2 3 5稍慢一些。但正如您下面可以看到的那样，它还是可以的。之后，时间越来越短，最佳列表为：
因此，我创建了一个新函数，但是使用的是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个测试：
$ 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;
}
我想我没有对代码进行优化，但还算公平。现在是测试阶段。由于有很多动态内存，我预计2 3 5列表会比硬编码的2 3 5稍慢一些。但正如您下面可以看到的那样，它还是可以的。之后，时间越来越短，最佳列表为：
2 3 5 7 11 13 17 19
用时8.6秒。因此，如果有人想创建一个使用这种技术的硬编码程序，我建议使用2 3和5列表，因为收益并不是很大。但是，如果愿意编写此列表也可以。问题是你不能声明所有情况而不使用循环，否则你的代码将会非常庞大（在相应的内部if中将有1658879个ORs，即||）。接下来的列表：
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. 我没有有意地释放内存，将此任务交给操作系统，因为当程序退出时，内存将被释放，以节省时间。但如果您打算在计算后继续运行代码，则最好将其释放。
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 ./testprimebool.x 18446744065119617029 7
h(2,3,5,7)
Yes, its prime.
real 0m9.123s
user 0m9.132s
sys 0m0.000s
- DrBeco
5
奖励：
101-199 的所有质数都在这里失败，因为 101 % (11+90)。 - vp_arth1需要在
n%(i+86) 处停止或检查 n > i+k。 - vp_arth干得好，先生。我会看一下的。谢谢。对于质数7、11、13、17、19、23和29，函数
check235()也会出现同样的问题。 - DrBeco解决方案：需要将这些提醒移动到一个数组中，迭代并在
i+arr[k] >= n 时中断迭代。 - vp_arth我考虑过这个，但我不想使用数组，因为带有常量的
if 语句可以更好地被编译器优化。我进行了编辑以添加一个异常并保持当前结构完整。但我同意，对于人眼来说，使用数组可能更好。 - DrBeco3
检查从2到待检查的数字的平方根的每个整数的模数。
如果模数等于零，则该数字不是质数。
伪代码：
bool IsPrime(int target)
{
for (i = 2; i <= root(target); i++)
{
if ((target mod i) == 0)
{
return false;
}
}
return true;
}
- Matt Lacey
5
2当然，缺点是每次迭代都要计算sqrt，这会大大减慢速度。 - Rich Bradshaw
9任何合理的编译器都应该能够检测到root(target)是一个循环不变量并将其提升。 - Stephen Canon
1（如果您使用的编译器无法进行这种优化，请务必报告错误，让编译器的作者知道他们错过了这种优化。） - Stephen Canon
除了许多其他可能的（微）优化之外，如果您在for语句之前手动获取sqrt，则还可以检查其模数（如果为0，则返回false）。 - Matt Lacey
2如果目标值是1怎么办？ - ffffff01
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;
}
- Vladimir Kocjancic
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）。另一方面，乘法则相当便宜。
- Olof Forshell
1
我正在使用 Miller/Rabin 算法来检查一个数字是否是质数。
#include <stdlib.h>
typedef size_t positive_number; // also try __uint128_t
static inline positive_number multiplication_modulo(positive_number lhs, positive_number rhs, positive_number mod) {
positive_number res = 0; // we avoid overflow in modular multiplication
for (lhs %= mod, rhs %= mod; rhs; (rhs & 1) ? (res = (res + lhs) % mod) : 0, lhs = (lhs << 1) % mod, rhs >>= 1);
return res; // <= (lhs * rhs) % mod
}
static int is_prime(positive_number n, int k) {
positive_number a = 0, b, c, d, e, f, g; int h, i;
if ((n == 1) == (n & 1)) return n == 2;
if (n < 51529) // fast constexpr check for small primes (removable)
return (n & 1) & ((n < 6) * 42 + 0x208A2882) >> n % 30 && (n < 49 || (n % 7 && n % 11 && n % 13 && n % 17 && n % 19 && n % 23 && n % 29 && n % 31 && n % 37 && (n < 1369 || (n % 41 && n % 43 && n % 47 && n % 53 && n % 59 && n % 61 && n % 67 && n % 71 && n % 73 && ( n < 6241 || (n % 79 && n % 83 && n % 89 && n % 97 && n % 101 && n % 103 && n % 107 && n % 109 && n % 113 && ( n < 16129 || (n % 127 && n % 131 && n % 137 && n % 139 && n % 149 && n % 151 && n % 157 && n % 163 && n % 167 && ( n < 29929 || (n % 173 && n % 179 && n % 181 && n % 191 && n % 193 && n % 197 && n % 199 && n % 211 && n % 223))))))))));
for (b = c = n - 1, h = 0; !(b & 1); b >>= 1, ++h);
for (; k--;) {
for (g = 0; g < sizeof(positive_number); ((char*)&a)[g++] = rand()); // random number
do for (d = e = 1 + a % c, f = n; (d %= f) && (f %= d););
while (d > 1 && f > 1);
for (d = f = 1; f <= b; f <<= 1);
for (; f >>= 1; d = multiplication_modulo(d, d, n), f & b && (d = multiplication_modulo(e, d, n)));
if (d == 1) continue;
for (i = h; i-- && d != c; d = multiplication_modulo(d, d, n));
if (d != c) return 0;
}
return 1;
}
测试是打印前几个质数:
#include <stdio.h>
int main() {
// C Fast Iterative Algorithm
// The First 10,000 Primes
for (int i = 0 ; i < 104730 ; ++i)
if (is_prime(i, 20))
printf("%d %c", i, (i+1) % 10 ? ' ' : '\n');
if (is_prime(9223372036854775783UL, 12))
if (is_prime(9223372036854775643UL, 12))
if (!is_prime(3037000493ULL * 3037000453ULL, 12))
printf("Done.\n");
}
你可以将它放入一个名为
primes.c的文件中，然后进行编译和执行：gcc -O3 -std=c99 -Wall -pedantic primes.c ; ./a.out ;
这种费马测试变体在log(n)中具有多项式运行时间。
__uint128_t类型可能会随着128位整数GCC扩展而提供。
- user13366325
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
i < number是多余的。根据定义，如果一个数x = a * b，那么要么a或b小于int(sqrt(x))，另一个大于它。因此，你的循环只需要执行到int(sqrt(x))即可。 - twalberg