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

这是为了problem on codeforces；当我提交此功能时，网站会打印“超出时间限制”。

Answer 1

您的代码的时间复杂度为 O(n/2) -> O(n)。如果 n 是 10^12，则检查 n 的素数大约需要 10000 秒（给定 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 > 开方（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

的平方根

c++ 判断一个数是否为质数的函数

c++ function to check if a number is a prime

c++

primes

time-limiting