Python计算素数个数的两种方法

素数（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 N<3:
        return 0
    else:
        cou = 1
        for i in range(3,N,2):
            if isPrime(i):
                cou += 1
    return cou
print(countPrime(2))
print(countPrime(5))
print(countPrime(100))
print(countPrime(100000))  
print(countPrime(10000000))#在n>100000000时达到计算瓶颈

输出：

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的倍数剔除掉；不断重复下去。

def couPrime(N):
   primeList = [True]*N
   for i in range(2,N):
       if(primeList[i]):
           for j in range(2*i,N,i):
               primeList[j]=False
   cou = primeList.count(True)-2
   return cou
print(couPrime(100000000)) #在n>1000000000达到计算瓶颈

输出：

5761455

来源：https://viper.blog.csdn.net/article/details/128961329