algorithm - 你是质数?

  显示原文与译文双语对照的内容
70 5

多年来,我一直在关注寻找更好的素数识别器的问题。我发现这是一个巨大的学术研究和研究- 我对这方面的兴趣只是为了好玩。这是我在( 下方) 中首次尝试的尝试。

我的问题是,你能推荐一个改进的( 我不引用网络上的其他引用,而是在寻找实际的C 代码)?我正在尝试从这一点上更好地了解如何确定解决方案的性能复杂性。

我认为这个解决方案的复杂性是 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("%dn", input);
 }
 factorFound = 0; 
 } 
 return returnValue;
}
时间:原作者:0个回答

63 0
 for (i = 2; i <= ceiling; i++) {
 if (input % i == 0) {
 factorFound = 1;
 break;
 } 
 }

这是对"相同"算法的第一次改进,仍然保持在算法的。它根本不需要任何数学来看这个。

除此之外,一旦看到 input 不能被 2整除,就无需检查 4,6,8,等等,如果任何偶数划分为 input,那么肯定是因为它分割了偶数。

如果你想在算法之外进行一点时间,你可以以使用一个像这样的循环。Cooper提供了他的答案。( 这比让他修改我的代码更容易,尽管他的工作非常感谢)

对于某些正整数 n 而言,除 2和 3以外的每个素数都是形式为 n*6 + 1 或者 n*6 - 1的情况。若要查看这里选项,请注意m = n*6 + 2或者m = n*6 + 4然后,n 可以被 2整除。ifm = n*6 + 3然后它可以被 3整除。

事实上,我们可以更进一步。ifp1, p2,.. , pk是第一个 k 素,然后所有与它的产品标记的整数都出现'插槽',所有剩余素都必须符合。

让我们看看,让 k# 成为所有素数的产品。如果gcd(k#, m) = ggn*k# + m 分开,因此如果 g!= 1,那么这个求和是很简单的组合。所以如果你想用 5# = 30 来迭代,那么你的互素整数是 1,7,11,13,17,19,23和0.

从技术上讲我没有证明我的最后一次声明。这并不难

ifg = gcd(k#, m)然后,对于任何整数,ng 都划分 n*k# + m,因为它划分了 k#,所以它还必须分割 n*k#但它也划分了 m 所以它必须把。上面我只是为 n = 1 证明的。我的错误。

另外,我应该注意,这一切都不会改变algoritm的基本复杂性,它仍然是( n^1/2 ) 。它所做的全部工作是的,减少了计算实际预期运行时间的系数。

原作者:
65 5

算法中每个素性测试的时间复杂度为 O(sqrt(n))

你可以始终使用除 2和 3以外的所有素数都是格式的事实: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位 int )的平方 root 。

此外,如果输入数相对较小,你可以尝试计算一个筛选器。

以下是两种想法的组合:

#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,开始处理查询之前。它运行得很快。

原作者:
...