有什么简单的方法可以让这个小程序更快吗？我已经完成了一个任务，它是正确的，但是太慢了。该程序的目的是打印第n对素数，其中两个素数之间的差是2，给定n。
#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方面有一些经验。
回答 4
Stack Overflow用户
发布于 2016-09-16 12:50:38
要找到相差2的素数对，您只需找到一个素数，然后添加2，并测试它是否也是素数。
if (isPrime(x) && isPrime(x+2)) { /* found pair */ }要找到素数，最好的算法是Sieve of Eratosthenes。您需要构建一个最高可达(N)的查找表，其中N是您可以获得的最大数量。如果一个数是质数，你可以使用筛子得到O(1)。在构建筛子时，您可以构建已排序素数的列表。
如果你的N很大，你也可以利用一个数P是素数的事实，如果它没有任何素数因子SQRT(P) (因为如果它有一个> <= (N)的因子，那么它也应该有一个< SQRT(N))。您可以构建一个大小为SQRT(N)的Eratosthenes筛子，以获得素数列表，然后测试这些素数中是否有任何一个除以P。如果没有一个除以P，则P是素数。
使用这种方法，您可以相对快速地测试高达10亿个左右的数字，并且只需要很少的内存。
Stack Overflow用户
发布于 2016-09-16 12:38:52
以下是在isPrime中加速循环的改进
bool isPrime(int number) {
for (int i = 3; i * i <= number; i += 2) { // Changed the loop condition
if (!(number%i)) {
return 0;
}
}
return 1;
}Stack Overflow用户
发布于 2016-09-16 12:47:30
您调用isPrime的频率过高。你写了
currentNummber = 3;
/* ... */
do {
currentNumber+=2;
} while (!isPrime(currentNumber));...which表示每个奇数都会调用isPrime。然而，当你确定5是质数时，你已经可以知道10，15，20等不会是质数，所以你不需要测试它们。
素数倍数的这种方法是在使用筛网过滤器时实现的，参见例如Sieve of Eratosthenes algorithm in C以C语言实现用于素数的筛网滤波器。
https://stackoverflow.com/questions/39531437
复制
腾讯云开发者
