查找下一个质数遇到执行错误（超出时间限制）

Question

有人知道程序为什么会崩溃吗？输入的是质数，你必须搜索下一个。如果输入非素数，则停止。谢谢。

#include <iostream>
using namespace std;
int nextprime (int);
bool primality (int);

int main () {
    int a;
    cin >> a;
    bool prime = primality(a);
    while (prime) {
        cout << nextprime(a) << endl;
        cin >> a;
        prime = primality(a);
    }
    
}
int nextprime (int x) {

    ++x;
    if (x % 2 == 0 and x != 2) ++x;
    bool prime = primality(x);
    while (not prime) {
        x = x + 2;  
        prime = primality (x);
    }
    return x;
    
}

bool primality (int x) {
    if (x % 2 == 0 and x != 2) return false;
    for (int number = 3; number*number <= x; number = number + 2) {
        if (x % number == 0) return false;
    }
    return true;
}

一切都适合我，即使是大素数。我不知道是什么导致它失败。它适用于我输入的所有内容，但“代码判断”仍然给出执行错误

Answer 1

速度略有提高。

更改此：

for (int number = 3; number*number <= x; number = number + 2) {
    if (x % number == 0) return false;
}

对此：

const int sqrtX = (int)(sqrt(x) + 1);
for (int number = 3; number <= sqrtX; number = number + 2) {
    if (x % number == 0) return false;
}

它在每次迭代中将

number*number

相乘，改为仅将

number

与

x

的平方根进行比较，后者仅计算一次。 确保

#include <math.h>

以便获得 sqrt 函数。

如果您不想编写埃拉托色尼筛法，您可以利用这样一个事实：您不仅可以跳过奇数，还可以跳过 3、5 和 7 的倍数。 您可以在我的 github 上参考我比平均速度更快的 isPrime 函数：https://github.com/jselbie/isprime/blob/master/isprime.cpp