python 代码

N=1000010
primes=[0]*N    #存质数
st=[False]*N    #是否被筛掉
def get_primes(n):
    cnt = 0  # 下标
    for i in range(2,n+1):
        if not st[i]:   #质数
            primes[cnt]=i   #存
            cnt+=1
            j=i*2   #从2倍i开始,因为小于i的倍数在之前的while循环中已经被筛掉了。
            while j<=n: #开始筛
                st[j]=True
                j+=i    #i的倍数筛 对应j=i*2
    print(cnt)
n=int(input())
get_primes(n)