你是一个素数 [英] Are You A Prime Number
问题描述
我一直希望找到一个更好的素数识别多年的问题。我意识到这是学术研究和研究的一个巨大的领域 - 我的这种兴趣是真的只是为了好玩。这是我在一个可能的解决方案的第一次尝试，在C（下图）。
我的问题是，你可以提出一个改进（未引述消息在网络上一些其他的参考，我在寻找实际的C code）？我试图从这个得到的是更好地了解确定这样一个解决方案的性能复杂性。
我是正确得出结论，这种解决方案的复杂度为O（n ^ 2）？
的#include＆LT; stdio.h中＆GT;
＃包括＆LT;文件math.h＆GT;
/ * isprime * /
/ *如果从标准输入列表中的每个数是素试验。 * /
/ *输出只会在列表打印素数。 * /
INT主（INT ARGC，字符* argv的[]）{
INT的returnValue = 0;
INT I;
INT上限;
INT输入= 0;
INT factorFound = 0;
而（scanf函数（％d个，和放大器;！输入）= EOF）{
上限=（INT）的sqrt（输入）;
如果（输入== 1）{
factorFound = 1;
}
对于（i = 2; I＆LT; =上限;我++）{
如果（输入％我== 0）{
factorFound = 1;
}
}
如果（factorFound == 0）{
的printf（％D \ N，输入）;
}
factorFound = 0;
}
返回的returnValue;
}
的（I = 2; I＆LT; =上限;我++）{
如果（输入％我== 0）{
factorFound = 1;
打破;
}
}
这是第一个改进，使仍然留相同的算法的范围内。它不需要任何的数学都看到这一点。
除此之外，一旦你看到输入是不是能被2整除，没有必要检查4，6，8，等等。如果任何偶数分到输入，那么可以肯定2将有，因为它把所有的偶数。
如果你想的算法步骤之外一点点，你可以使用像一个的谢尔顿L.库珀提供了他的答案。 （这仅仅是不是让他改正我的code的意见，虽然他的努力是多少AP preciated容易）
这需要一个事实，即每一个素除2和3的形式的优点 N * 6 + 1 或 N * 6 - 1 为正整数 N 。看到这一点，只是注意，如果 M = N * 6 + 2 或 M = N * 6 + 4 ，那么 N 是整除2.如果 M = N * 6 + 3 则是被3整除。
其实，我们可以进一步利用这个。如果 P1，P2，...，PK 是第 K 素数，那么所有的互质的整数他们的产品标注了插槽，所有剩余的素数必须适应。
要看到这一点，才让 K＃全部素数的乘积高达 PK 。那么如果 GCD（K＃，M）= G ，先按g 分歧 N * K＃ + M 键，所以这和是平凡复合如果摹！= 1 。所以，如果你想在 5＃= 30 ，那么你的互质是1，7，11，13，17，19，23和29。
从技术上来说，我没有证明我最后的要求。这不是要困难得多
如果 G = GCD（K＃，M），那么对于任意整数， N ，先按g 分歧 N * K＃+ M ，因为它把 K＃等等它也必须分 N * K＃。但是它也把 M 以及因此它必须分裂的总和。以上我只是证明了它 N = 1 。我的坏。
另外，我要指出，这一切都不是改变algoritm的根本复杂性，它仍然将是为O（n ^ 1/2）。所有它做的是大幅的减少了被用来计算实际预期的运行时间系数。
I've been interested in the problem of finding a better prime number recognizer for years. I realize this is a huge area of academic research and study - my interest in this is really just for fun. Here was my first attempt at a possible solution, in C (below).
My question is, can you suggest an improvement (without citing some other reference on the net, I'm looking for actual C code)? What I'm trying to get from this is a better understanding of determining performance complexity of a solution like this.
Am I right in concluding that the complexity of this solution is O(n^2)?
#include <stdio.h>
#include <math.h>
/* isprime */
/* Test if each number in the list from stdin is prime. */
/* Output will only print the prime numbers in the list. */
int main(int argc, char* argv[]) {
int returnValue = 0;
int i;
int ceiling;
int input = 0;
int factorFound = 0;
while (scanf("%d", &input) != EOF) {
ceiling = (int)sqrt(input);
if (input == 1) {
factorFound = 1;
}
for (i = 2; i <= ceiling; i++) {
if (input % i == 0) {
factorFound = 1;
}
}
if (factorFound == 0) {
printf("%d\n", input);
}
factorFound = 0;
}
return returnValue;
}
for (i = 2; i <= ceiling; i++) {
if (input % i == 0) {
factorFound = 1;
break;
}
}
This is the first improvement to make and still stay within the bounds of "same" algorithm. It doesn't require any math at all to see this one.
Beyond that, once you see that input is not divisible by 2, there is no need to check for 4, 6, 8, etc. If any even number divided into input, then surely 2 would have because it divides all even numbers.
If you want to step outside of the algorithm a little bit, you could use a loop like the one that Sheldon L. Cooper provides in his answer. (This is just easier than having him correct my code from the comments though his efforts are much appreciated)
this takes advantage of the fact that every prime other than 2 and 3 is of the form n*6 + 1 or n*6 - 1 for some positive integer n. To see this, just note that if m = n*6 + 2 or m = n*6 + 4, then n is divisible by 2. if m = n*6 + 3 then it is divisible by 3.
In fact, we can take this further. If p1, p2, .., pk are the first k primes, then all of the integers that are coprime to their product mark out 'slots' that all remaining primes must fit into.
to see this, just let k# be the product of all primes up to pk. then if gcd(k#, m) = g, g divides n*k# + m and so this sum is trivially composite if g != 1. so if you wanted to iterate in terms of 5# = 30, then your coprime integers are 1, 7, 11, 13, 17, 19, 23 and 29.
technically, I didn't prove my last claim. It's not much more difficult
if g = gcd(k#, m), then for any integer, n, g divides n*k# + m because it divides k# so it must also divide n*k#. But it divides m as well so it must divide the sum. Above I only proved it for n = 1. my bad.
Also, I should note that none of this is changing the fundamental complexity of the algoritm, it will still be O(n^1/2). All it is doing is drastically reducing the coefficient that gets used to calculate actual expected run times.
这篇关于你是一个素数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
