你是一个素数

Question

多年来,我一直对寻找更好的素数识别器的问题感兴趣.我意识到这是一个巨大的学术研究和学习领域 - 我对此感兴趣只是为了好玩.这是我在C(下面)中首次尝试可能的解决方案.

我的问题是,你能否提出一个改进(没有引用网上的其他参考,我正在寻找实际的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("%d\n", input);
        }

        factorFound = 0;    
    } 

    return returnValue;
}

Answer 1

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

这是第一个改进,仍然保持在"相同"算法的范围内.它根本不需要任何数学就可以看到这个.

除此之外,一旦你看到它input不能被2整除,就没有必要检查4,6,8等等.如果任何偶数被分成input,那么肯定会有2,因为它除了所有偶数.

如果你想稍微超出算法的范围,可以使用Sheldon L. Cooper在答案中提供的循环.(这比让他从评论中纠正我的代码更容易,尽管他的努力非常受欢迎)

这利用了除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,所以这个总和是简单的复合if g != 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.我的错.

另外,我应该注意到,这一切都没有改变算法的基本复杂性,它仍然是O(n ^ 1/2).它所做的只是大幅减少用于计算实际预期运行时间的系数.

Answer 2

算法中每个素性测试的时间复杂度为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位整数).

此外,如果输入数字相对较小,您可以尝试计算筛子.

以下是两种想法的组合:

#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在开始处理查询之前,在程序开头调用.它运行得非常快.