OP的方法消耗大量时间,因为它不利用不需要确定余数,如果i不是素数。
for (i=2; i*i<=number; i++) {
if (number % i == 0) return 0;
该Sieve_of_Eratosthenes可能会更快,但是从OP的代码是一个戏剧性的变化。
怀疑这个代码对于OP来说仍然太慢。
以下仅通过尝试对先前找到的素数进行测试来调整OP的代码。它也使用pcandidate/plist[index]作为终止条件的一部分。一旦计算出pcandidate % plist[index],经过优化的编译器通常可以以很小的成本提供这个功能。
bool prime_test(const unsigned long *plist, unsigned long long pcandidate) {
if (pcandidate <= 2) return pcandidate == 2;
for (size_t index = 0; ; index++) {
unsigned long long remainder = pcandidate % plist[index];
if (remainder == 0) return false;
unsigned long long quotient = pcandidate/plist[index];
if (quotient < plist[index]) return true;
}
assert(0);
return true;
}
unsigned long long prime_nth(size_t n) {
unsigned long plist[n+1];
plist[0] = 2;
unsigned long long pcandidate = plist[0];
for (size_t index = 0; index <= n; index++) {
while (!prime_test(plist, pcandidate)) pcandidate++;
plist[index] = (unsigned long) pcandidate;
pcandidate++;
}
return plist[n];
}
一个经典的简化只涉及在奇数中寻找新的素数。将所有数学变为unsigned。留给OP。