C语言 C - 如何轻松测试它是否是素数？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/5281779/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
C - how to test easily if it is prime-number?
提问by Waypoint
Possible Duplicates:
C - determine if a number is prime
可能的重复项：
C - 确定一个数是否为素数
Is there any way to test easily in C whether a selected number is prime or not?
有没有办法在 C 中轻松测试所选数字是否为素数？
回答by vissi
The easiest way is writing a loop, like:
最简单的方法是编写一个循环，例如：
int is_prime(int num)
{
if (num <= 1) return 0;
if (num % 2 == 0 && num > 2) return 0;
for(int i = 3; i < num / 2; i+= 2)
{
if (num % i == 0)
return 0;
}
return 1;
}
You can then optimize it, iterating to floor(sqrt(num)).
然后你可以优化它，迭代到floor(sqrt(num)).
回答by rsc
You could try to use Sieve of Eratosthenes:
您可以尝试使用埃拉托色尼筛法：
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
Easily you will find various implementations of this algorithm.
很容易你会发现这个算法的各种实现。
回答by paxdiablo
The fastestway is to precalculate a bit array (indicating prime/nonprime) of all possible integers in the range you're interested in. For 32-bit unsigned integers, that's only 512M, which will easily fit in modern address spaces (and, even if it didn't, it would be a fast file lookup).
该最快的方法是预先计算了一下阵列（表示黄金/非高峰）范围内的所有可能的整数你感兴趣的。对于32位无符号整数，这是只有512M，这将很容易适应现代地址空间（和，即使没有，这也将是一个快速的文件查找）。
This will almost certainly be faster than calculating it via a sieve each time.
这几乎肯定比每次都通过筛子计算要快。
