Posts pythonTip 87 质数的数目
Post
Cancel

pythonTip 87 质数的数目

题目描述: 给你一个正整数N(1 <= N <= 10000000),求{1,2,3,…,N}中质数的个数。 如N=3, 输出2.

示例: 输入: N = 1 输出: 0

分析:

参考 chenxw4tm 大佬 的思路.

用一个list(L),把不是 素数的都标成0,其他都是素数标1

有几个注意点:

1、大于6的素数都在 6 的倍数前后,所以6个一组标[1,0,0,0,1,0]*(N/6) 有些6k+1/6k+5可能不是素数,先初始化为1

2、从小到大(2,3因为条件1已经排除,从5,7……开始)不断把素数p的倍数弄成0,剩下的就是所有素数。

但是第二步有些简单的精细:

​ 1、不需要每次用数学方法判断p是不是素数,因为L优化完前一个p以后,排在p以后,值为1的那个下标自然是下一个要优化的素数

​ 2、优化的素数也不是2-N,二是2到根号N

​ 3、每次优化,也不是从2p,3p这样优化,二是p*pp*p+2pp*p+4p……,因为p*(p-1)这项,肯定有p-1这个比p小的因子,肯定已经优化过了,而p*p+p之类都是偶数,初始化已经为0了

​ 4、每次找下一个素数,步长设为2,不是1,因为都是奇数。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def f(N):
    fir=[0,0,1,1,0,1,0]
    L = [0 for _ in range(N+1)]
    L[:7] = fir
    if N<=6:
        return sum(L[:N+1])
    else:
        # [1,0,0,0,1,0]*(N/6)  也就是模仿这一步
        for i in range(5, N+1):
            if (i-1) % 6 == 0 or (i+1) % 6 == 0:
                L[i] = 1
        z=5
        while z<=int(N**0.5):
            if L[z]==1:
                for j in range(z*z,N+1,2*z):
                    L[j]=0
            z=z+2
    return sum(L)   
print(f(N))
This post is licensed under CC BY 4.0 by the author.
Trending Tags
Contents

pythonTip 86 修剪数列

pythonTip 88 数字转换

Trending Tags