用于检查数字是否为素数的C++函数

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=999999999989。

这是针对problem on codeforces的；当我提交此函数时，网站会打印超出时间限制。

---

解决方案

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

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的平方根