python-找素数

解题思路:

首先分析题目：

问题1：数据较大，如果遍历依次判断素数的话，会超时。

解决方法：埃拉托色尼筛选法。原文链接：https://blog.csdn.net/xiaoquantouer/article/details/51817803

问题2：在解题的过程中，我们还会遇到一个问题，就是数组的空间大小问题，如果我们开辟一个大小为(R+1)的数组，然后利用埃拉托色尼筛选法，内存超限。

解决方法：缩小数组空间，此时利用数学知识，将[L,R] 对应到[0,R-L]。

假设L<=p<=R，p为素数，那么在[L,R]之间的所有的p的倍数都是合数（这里至少为2倍）。

我们可以找到找到一个最小倍数k使得k*p在[L,R]之间。k = L/p (向上取整)，对应到[0,R-L]之中就是k*p-L，然后k的值不断递加1。对应未转化时去除在[L,R]中的p的倍数。

解决了以上两个问题之后就能解答了。

注意事项:

参考代码:

from math import ceil  
from math import sqrt  
  
def f(l,r):  
    Check = [True]*1000001    #埃拉托色尼筛选法筛选范围
    res = [True]*1000001      #[L,R]转化后的对应空间
    p = 2  
    while p*p <= r:  
        if Check[p]:  
            for i in range(2*p,int(sqrt(r))+1,p):  
                Check[i] = False  
        k = ceil(l/p)    #找到最小倍数，向上取整
        while k * p <= r:  
            if k != 1:  
                res[k*p-l] = False   #去除合数
            k = k + 1  
        p = p + 1  
          
    ans = res[:r-l+1]    #求出转化后空间素数的个数
    print(ans.count(True))  
                      
  
if __name__ == '__main__':  
    l,r = map(int,input().strip().split())  
    f(l,r)