快速判断素数的算法（比根号N的复杂度更快）_找素数 i*i 和sqrt谁快

作者：小小林熬夜学编程 | 2024-02-10 19:25:15

踩

找素数 i*i 和sqrt谁快

素数有这样一个规律：大于等于5的质数一定和6的倍数相邻。例如5和7，11和13等。
证明过程如下：

因此，我们将所有输入的大于等于5的数据以上述方式表示，将其除以6，若余数不为1或5，则直接证明其不是素数，剩下的再进行从1遍历到√N的判断，注意步长为6：

Python3 代码


from math import sqrt,floor
def prime(num) :
    
    if num == 2 or num == 3 : return True
    
    if num % 6 != 1 and num % 6 != 5 : return False
 
    for i in range(5,floor(sqrt(num))+1,6) :
        if num % i == 0 or num % (i+2) == 0 : return False
        
    return True

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/小小林熬夜学编程/article/detail/75259