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

2022-05-12 00:00:00 primes c++ time-limiting
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的平方根

相关文章