Python小技巧:计算素数个数 | 您所在的位置:网站首页 › python怎么算质数 › Python小技巧:计算素数个数 |
计算小于N的素数个数
方法一:直接判断方法二:埃氏筛法
素数(prime number)也叫质数,为大于1的且除1和本身以外不再有其他因数的自然数,与之相对的是合数,素数有无限个。 计算小于N的素数个数 输入: 10输出: 4小于10的素数共4个:2, 3, 5, 7 方法一:直接判断 from math import sqrt def isPrime(n): for i in range(2,int(sqrt(n))+1): if n%i==0: return False return True def countPrime(N): if N100000000时达到计算瓶颈输出: 0 2 25 9592 664579 方法二:埃氏筛法埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法,是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.~194B.C.)提出的一种筛选法。 要得到自然数n以内的全部素数,必须把不大于n的所有素数的倍数剔除,剩下的就是素数,具体步骤如下:先用2去筛,即把2留下,把2的倍数剔除掉;再用下一个质数,也就是3筛,把3留下,把3的倍数剔除掉;接下去用下一个质数5筛,把5留下,把5的倍数剔除掉;不断重复下去。 输出: 5761455 |
CopyRight 2018-2019 实验室设备网 版权所有 |