蓝桥杯算法提高VIP-找素数(埃氏筛法)

解题思路:

首先定义一个a数组,作用是对2到sqrt(R)的数进行进行筛选,其中a[num]=True 表示a数组中数字num是素数,若等于False 则是合数,a有默认值a[1]=False,和a[2]=True,然后num从2开始判断,先去掉2的倍数(素数的倍数一定是合数)，然后num=3,再去掉3的倍数，再去掉4的倍数，……依此类推，最后剩下的就是素数。

这里注意的是,每次求素数的倍数,比如素数3,我们进行删选时是从他的3倍开始的,因为前面素数2时,把两倍的都去除了(这里的去除就是赋值为False),我们去除L到R中素数的倍数的时候,确定一个最小倍数,比如素数2 在L=5,R=10 时,最小倍数是3使得2*3=6在L到R中,然后让res[2*3-5]=Fasle,这里坐标L->0这样就行,具体看代码

注意事项:见代码注释

参考代码:

import math
L,R=map(int,input().split())
#求出judNums中的素数,则该素数的倍数在nums中一定是合数
#不是素数为False,素数是True
a=[True]*1000001
res=[True]*1000001
a[1],a[2]=False,True
i=2
while i*i<=R:
    #如果是素数
    if a[i]:
        #那么i的倍数就是合数(下面i*j就是i的倍数)
        j=2
        while j*i<math.sqrt(R):
            a[i*j]=False
            j+=1
        #向上取整(这里注意是L/i,而不是L//i)
        k=math.ceil(L/i)
        #求i在res中的倍数
        while k*i<=R:
            #如果k=1,说明i=L,那么一直对res[0]
            if k!=1:
                res[k*i-L]=False
            k+=1
   
    i+=1
res=res[:R-L+1]
print(res.count(True))