本文最后更新于 768 天前,其中的信息可能已经有所发展或是发生改变。
最近研究了个任意区间内质数求和的问题,顺带研究了下如何判断质数,在此做个记录。
一、全部穷举,强行判断
根据质数的定义,对于任意正整数 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;
}