你是一个素数
我对多年来寻找更好的素数识别器的问题感兴趣。 我意识到这是一个巨大的学术研究和研究领域 – 我对此感兴趣只是为了好玩。 这是我在C（下面）中首次尝试可能的解决方案。
我的问题是，你能否提出一个改进（没有引用网上的其他参考，我正在寻找实际的C代码）？ 我想从中获得的是更好地理解确定这样的解决方案的性能复杂性。
我是否正确地得出结论，这个解决方案的复杂性是O（n ^ 2）？
#include #include /* 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; } }
这是第一个改进，仍然保持在“相同”算法的范围内。 它根本不需要任何数学来看这个。
除此之外，一旦你看到input不能被2整除，就没有必要检查4,6,8等。如果任何偶数被分成input ，那么肯定会有2，因为它除了所有偶数。
如果你想稍微超出算法的范围，可以使用像Sheldon L. Cooper在答案中提供的循环。 （这比让他从评论中纠正我的代码更容易，尽管他的努力非常受欢迎）
这利用了以下事实：对于某些正整数n除了2和3之外的每个素数都是n*6 + 1或n*6 - 1 6-1的forms。 要看到这一点，请注意，如果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 ，因此如果g != 1则该和是非常复合的。 所以如果你想用5# = 30进行迭代，那么你的互质整数分别是1,7,11,13,17,19,23和29。
从技术上讲，我没有certificate我的最后一项主张。 这并不困难
如果g = gcd(k#, m) ，那么对于任何整数， n ， g除n*k# + m因为它除了k#所以它也必须除n*k# 。 但它也除了m ，所以它必须除以总和。 上面我只certificate了n = 1 。 我的错。
另外，我应该注意到，这一切都没有改变算法的基本复杂性，它仍然是O（n ^ 1/2）。 它所做的只是大幅减少用于计算实际预期运行时间的系数。
算法中每个素性测试的时间复杂度为O(sqrt(n)) 。
您总是可以使用以下事实：除了2和3之外的所有素数都是以下forms： 6*k+1或6*k-1 。 例如：
int is_prime(int n) { if (n <= 1) return 0; if (n == 2 || n == 3) return 1; if (n % 2 == 0 || n % 3 == 0) return 0; int k; for (k = 6; (k-1)*(k-1) <= n; k += 6) { if (n % (k-1) == 0 || n % (k+1) == 0) return 0; } return 1; }
此优化不会改善渐近复杂度。
编辑
鉴于您在代码中反复测试数字，您可能需要预先计算素数列表。 只有4792个素数小于或等于INT_MAX的平方根（假设为32位整数）。
此外，如果输入数字相对较小，您可以尝试计算筛子 。
以下是两种想法的组合：
#define UPPER_BOUND 46340 /* floor(sqrt(INT_MAX)) */ #define PRIME_COUNT 4792 /* number of primes <= UPPER_BOUND */ int prime[PRIME_COUNT]; int is_prime_aux[UPPER_BOUND]; void fill_primes() { int p, m, c = 0; for (p = 2; p < UPPER_BOUND; p++) is_prime_aux[p] = 1; for (p = 2; p < UPPER_BOUND; p++) { if (is_prime_aux[p]) { prime[c++] = p; for (m = p*p; m < UPPER_BOUND; m += p) is_prime_aux[m] = 0; } } } int is_prime(int n) { if (n <= 1) return 0; if (n < UPPER_BOUND) return is_prime_aux[n]; int i; for (i = 0; i < PRIME_COUNT && prime[i]*prime[i] <= n; i++) if (n % prime[i] == 0) return 0; return 1; }
在开始处理查询之前，在程序开头调用fill_primes 。 它运行得非常快。
你的代码只有复杂度O（sqrt（n）lg（n））。 如果你假设基本的数学运算是O（1）（直到你开始使用bignums为真），那么它只是O（sqrt（n））。
注意，素数测试可以在比O（sqrt（n）lg（n））更快的时间内执行。 该站点具有许多AKS素性测试的实现，已经certificate它在O（（log n）^ 12）时间内运行。
还有一些非常非常快速的probalistic测试 – 虽然速度很快，但它们有时会给出错误的结果。 例如， 费马素性测试 ：
给定一个数
p我们要测试素数，选择一个随机数a，并测试a^(p-1) mod p = 1。 如果为假，则p绝对不是素数。 如果为真，p可能是素数。 通过用a的不同随机值重复测试，可以降低误报的概率。
请注意，此特定测试有一些缺陷 – 有关详细信息，请参阅Wikipedia页面，以及您可以使用的其他概率素性测试。
如果你想坚持当前的方法，仍然可以进行一些小的改进 – 正如其他人所指出的那样，在2之后，所有进一步的素数都是奇数，所以你可以一次跳过两个潜在的因素。环。 当您找到一个因素时，您也可以立即突破。 但是，这不会改变算法的渐近最坏情况行为，它保持在O（sqrt（n）lg（n）） – 它只是改变最佳情况（到O（lg（n））），并且将常数因子减少大约一半。
一个简单的改进是在找到一个因子时将for循环更改为break：
for (i = 2; i <= ceiling && !factorFound; i++) { if (input % i == 0) { factorFound = 1;
另一种可能性是将计数器增加2（在检查2本身之后）。
你能建议改进吗？
在这里你去…不是算法，而是程序本身:)
- 如果您不打算使用
argc和argv，请删除它们 - 如果输入“fortytwo”怎么办？ 比较scanf（）
== 1，而不是!= EOF - 无需
sqrt()的值 - 不需要
returnValue，可以返回一个常量：return 0; - 而不是将所有function都放在
main()函数中，而是将程序与您能想到的function分开。
您可以对算法进行小幅削减，而不会增加太多的代码复杂性。 例如，您可以跳过validation中的偶数，并在找到因素后立即停止搜索。
if (input < 2 || (input != 2 && input % 2 == 0)) factorFound = 1; if (input > 3) for (i = 3; i <= ceiling && !factorFound; i += 2) if (input % i == 0) factorFound = 1;
关于复杂性，如果n是你的输入数字，那么复杂性不是O（sqrt（n）），因为你大致在大多数sqrt（n）分区和比较中做了吗？
偶数（2除外）不能是素数。 因此，一旦我们知道数字不均匀，我们就可以检查奇数是否是它的因素。
for (i = 3; i <= ceiling; i += 2) { if (input % i == 0) { factorFound = 1; break; } }
程序的时间复杂度为O(n*m^0.5) 。 用n表示输入中的素数。 并且m是输入中最大素数的大小，如果您愿意，则为MAX_INT 。 所以复杂性也可以写成O(n)其中n要检查的素数。
对于Big-O， n （通常）是输入的大小，在您的情况下，这将是要检查的素数。 如果我将这个列表的两倍大（例如重复它），它将花费（+ – ）两倍的长度，因此O(n) 。
这是我的算法，Complexity仍为O(n^0.5)但我设法删除代码中的一些昂贵的操作……
算法最慢的部分是modulus运算，我设法消除sqrt或做i * i <= n
这样我就节省了宝贵的周期......它基于sum of odd numbers is always a perfect square.
既然我们正在迭代odd numbers ，为什么不利用它呢？ 🙂
int isPrime(int n) { int squares = 1; int odd = 3; if( ((n & 1) == 0) || (n < 9)) return (n == 2) || ((n > 1) && (n & 1)); else { for( ;squares <= n; odd += 2) { if( n % odd == 0) return 0; squares+=odd; } return 1; } }
#include #include int IsPrime (int n) { int i, sqrtN; if (n < 2) { return 0; } /* 1, 0, and negatives are nonprime */ if (n == 2) { return 2; } if ((n % 2) == 0) { return 0; } /* Check for even numbers */ sqrtN = sqrt((double)n)+1; /* We don't need to search all the way up to n */ for (i = 3; i < sqrtN; i += 2) { if (n % i == 0) { return 0; } /* Stop, because we found a factor! */ } return n; } int main() { int n; printf("Enter a positive integer: "); scanf("%d",&n); if(IsPrime(n)) printf("%d is a prime number.",n); else printf("%d is not a prime number.",n); return 0; }
没有办法改进算法。 可能有很小的方法来改进您的代码，但不是算法的基本速度（和复杂性）。
编辑：当然，因为他不需要知道所有因素，只要它是否是素数。 好点。