c++函数来检查一个数字是否是素数

Question

bool prime (long long int n) {
bool prime = 1;
if (n == 1) {
return 0;
}
else {
for (long long int i = 2; i <= n/2 ; i++) {
if (n % i == 0) {
prime = 0;
break ;
}

}
return prime;
}
}

这是我检查n是否为素数的函数。它一直有效，直到我尝试一个12位数的数字，比如n=9999999999 89。

这是针对代码部队的问题；当我提交这个功能时；超过时间限制"；。

Answer 1

您的代码的时间复杂度为O(n/2(->O(n(。如果n是10^12，则需要大约10000秒来检查n的素性(给定1秒只能进行大约10^8的运算(。

for (long long int i = 2; i <= n/2 ; i++) {
if (n % i == 0) {
prime = 0;
break ;
}

这里的技巧是，你不需要检查i从2到n/2。相反，您可以将其从2减少到sqrt(n(。这是因为由于sqrt(n(*sqrt(n(是n，所以不应该有任何x和y，所以x>sqrt(n(；y>sqrt(n(；x*y=n。因此，如果n的除数存在，则它应该<=sqrt(n(。

所以你应该把你的循环换成这个

for (long long int i = 2; i*i <= n ; i++) {
if (n % i == 0) {
prime = 0;
break ;
}
}

这个代码的时间复杂度是O(sqrt(n((，这对于n应该足够了=10^12。

p.S：sqrt(n(表示n 的平方根