如何在 C 中实现更快的素数搜索算法

Question

首先，我对C还算陌生，对C++一无所知，只看了w3schools.org的C教程，并做了一些练习程序。 我正在寻找的是一些简单的东西，可以在半小时内找到从 1 到 1000000 的所有素数。 我不知道如何实现任何复杂的东西，比如Sieve of Atkin或其他复杂的算法。 您能否更简单地解释阿特金筛法（就像用外行术语一样）或用 C 语言演示它？请记住，我刚刚参加了 w3schools 的 C 初学者课程。

我使用的代码如下：

#include <stdio.h>

int n = 0, i, b, e, flag = 0;

int main() {
    printf("Enter a positive integer that will be the higher bound: ");
    scanf("%d", &b);

    for (n = 0; n < b; n++) {
        if (n == 0 || n == 1) {
        flag = 1;
        }
      for (i = 2; i <= n / 2; ++i) {
        if (n % i == 0) {
          flag = 1;
        }
      }
      if (flag == 0) {
        printf("%d is a prime number.\n", n);
        } else {
        }
        flag = 0;
    }
  return 0;
}

Answer 1

OP 的代码使用

for (i = 2; i <= n / 2; ++i) {

限制因素测试 - 一个适度的第一步。

然而，超过

n

的平方根，就没有因子了。由于根（通常）比

n/2

小，所以速度快很多。

我们可以使用

test_factor * test_factor <= n

，但是

test_factor * test_factor

可能会溢出。 使用

test_factor <= n/test_factor

。 智能编译器会看到附近的

n/test_factor

和

n%test_factor

并发出与其中之一执行速度差不多的代码。

代码可以计算

int limit = sqrt(n)

，但是 1) 存在边缘情况问题，因为

sqrt()

可能无法返回准确所寻求的根，即使它是整数 2) 当整数类型具有更高精度时，可能会丢失所需的进动那个

double

。 3) 产生浮点成本，而几乎没有额外成本

test_factor <= n/test_factor

。

OP 的代码在找到一个因素时设置一个标志，然后继续寻找更多因素。 但没有理由继续寻找。 一旦找到一个因素，这会大大加快退出循环的速度。

我们还可以检查所有其他值，因为除以 2 的数字不是质数 - 但有一个例外：2。这是一个适度的改进。

bool is_prime(int n) {
  if (n % 2 == 0) {
    return n == 2;
  }
  for (int test_factor = 3; test_factor <= n / test_factor; test_factor += 2) {
    if (n % test_factor == 0) {
      return false;
    }
  }
  return n > 1;  // No factors and n is more than 1.
}

使用

for (n = 2; n < b; n++) {
  if (is_prime(n)) {
    printf("%d is a prime number.\n", n);
  }
}

注意：不到2秒即可打印所有小于1000000的素数。

---

对于筛子方法。请参阅埃拉托斯特尼筛法伪代码。

Answer 2

有用的提示： 1.如果n不是2但能除以2则不是质数。 2. 检查可能的除数直到 sqrt(n) 就足够了。 3. 如果 n 是奇数，那么我们可以跳过所有偶数除数 4. 一旦找到第三个约数，就无需继续检查。

#include <math.h>
...
int is_prime = 1, n, i;
...
if (n < 0) n = -n;
if(n < 2 || (n != 2 && n % 2 == 0))
is_prime = 0;
else {
int sqrt_n = sqrt(n);
for(i = 3; i <= sqrt_n; i+=2)
if(n % i == 0){
is_prime = 0;
break;
}
}