用于检查数字是否为素数的C++函数 [英] c++ function to check if a number is a prime

查看:79
本文介绍了用于检查数字是否为素数的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的平方根

这篇关于用于检查数字是否为素数的C++函数的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆