题目

算法

本题用python写不能用一般的算法去求会超时，应该采用欧拉素数筛选法去求，算法复杂度为O（n）比其他的算法优秀的多，
算法思想:
（1）我们安排一个数组或者列表表示某个数是否为素数，最开始假设所有数都是素数
（2）核心思想是用最小质因数去筛选，我们另设一个列表，这个列表是用来存放已经筛选号的素数的，之后我们去遍历元素从2一直到n这些数，当这些数的标志是素数时纳入素数表中，无论他是与不是素数都与前面已经加入的素数去乘积，将这些乘积标志为非负数，但要注意不是一直与前面所有的素数相乘，而是要判断何时不要继续了，别忘了前面说过用最小质因子去筛选，避免重复所以当这个数i已经有了前面素数的因子时就不能再继续了，如果再继续就可能会造成重复，算法不是最优的了，例如 我们已经纳入素数表的 2，3，5， 现在是6这个数 6和2组合能帮助排除12，但不能去排除18 原因就是2是12的最小因子，但是18 3是最小因子，所以也就是说到6%2==0的时候就不能继续下去了。
代码如下:

def prime_list(n):
    a=(100001)*[0]
    b=(n+1)*[None]
    count=0
    for i in range(2,n+1):
        if a[i]==0:
            b[count]=i
            count+=1
        j=0
        while(j<count and i*b[j]<=n):
            a[i*b[j]]=1
            if(i%b[j]==0):
                break
            j+=1
    geshu=0
    for i in range(0,count-1):
        if b[i+1]-b[i]==2:
            geshu+=1
    print(geshu)   

a=int(input())
prime_list(a)