判断质数

最近研究了个任意区间内质数求和的问题,顺带研究了下如何判断质数,在此做个记录。

一、全部穷举,强行判断

根据质数的定义,对于任意正整数 n(n不小于1),若在 (1,n) 内不存在整数 a ,使 n%a==0 ,则 n 为质数。

那么,通过以下代码即可“轻易”判断一个数是否为质数:

bool check_prime(unsigned int num){
    if (num <= 1){
        return false;
    }
    for (unsigned long int j = 2; j <= num ; ++j) {
        if (num%j==0){
            return false;
        }
    }
    return true;
}
 def check(v:int) -> bool:
    if v <= 1:
        return False
    for i in range(2, v1):
        if v%i == 0:
            return False
    return True

二、部分穷举,较快判断

事实上,很容易得出任意合数的各因数关于其算术平方根对称,因此可缩小穷举范围:

bool check_prime(unsigned int num){
    if (num <= 1){
        return false;
    }
    int d = sqrt(num);
    for (unsigned long int j = 2; j <= d ; ++j) {
        if (num%j==0){
            return false;
        }
    }
    return true;
}

知识共享许可协议

本作品(《判断质数》由 gggxbbb)采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。


转载请注明出处: https://evax.top/2021/06/06/pan-duan-zhi-shu.html

暂无评论

发送评论 编辑评论

上一篇
下一篇