判断质数

gggxbbb 51 2021-06-06

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

一、全部穷举,强行判断

根据质数的定义,对于任意正整数 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;
}

# Python3 # C++