c - 如何使这个非常小的 C 程序更快？

Question

有什么简单的方法可以让这个小程序更快吗？我已经为作业做了它，它是正确的，但太慢了。该程序的目标是打印第 n 对素数，其中给定 n，两者之间的差为 2。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

bool isPrime(int number) {
  for (int i = 3; i <= number/2; i += 2) {
    if (!(number%i)) {
      return 0;
    }
  }

  return 1;
}

int findNumber(int n) {
  int prevPrime, currentNumber = 3;

  for (int i = 0; i < n; i++) {   
    do {
      prevPrime = currentNumber;  

      do {                               
        currentNumber+=2;
      } while (!isPrime(currentNumber));

    } while (!(currentNumber - 2 == prevPrime));
  }

  return currentNumber; 
}

int main(int argc, char *argv[]) {
  int numberin, numberout;
  scanf ("%d", &numberin);

  numberout = findNumber(numberin);

  printf("%d %d\n", numberout - 2, numberout);
  return 0;
}

我考虑使用某种数组或列表，其中包含直到当前数字为止找到的所有素数，并将每个数字除以该列表而不是所有数字，但我们还没有真正涵盖这些不同的数据结构，所以我觉得我应该能够解决这个问题，无需。我刚刚开始接触 C，但我在 Python 和 Java 方面有一些经验。

Answer 1

要找到相差 2 的素数对，只需找到一个素数，然后添加 2 并测试它是否也是素数。

if (isPrime(x) && isPrime(x+2)) { /* found pair */ }

要找到素数，最好的算法是 Sieve of Eratosthenes 。您需要构建一个最多 (N) 的查找表，其中 N 是您可以获得的最大数字。如果数字是质数，则可以使用 Sieve 获得 O(1)。在构建筛子时，您可以构建一个排序素数列表。

如果你的 N 很大，你也可以从数字 P 是素数这一事实中获益，如果它没有任何素数因子 <= SQRT(P) (因为如果它有一个因子 > SQRT(N) 那么它还应该有一个 < SQRT(N))。您可以构建大小为 SQRT(N) 的埃拉托斯特尼筛法来获取素数列表，然后测试这些素数中是否有任何素数能整除 P。如果没有一个能整除 P，则 P 是素数。

通过这种方法，您可以相对快速地测试高达 10 亿左右的数字，并且占用的内存很少。