判断质数 - Nothing

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

一、全部穷举，强行判断

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

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

C++

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;
}

Python

 def check(v:int) -> bool:
    if v <= 1:
        return False
    for i in range(2, v1):
        if v%i == 0:
            return False
    return True

二、部分穷举，较快判断

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

C++

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;
}