自测-2 素数对猜想

文章预览：

• 题目
• ���法

  题目

  算法

  本题用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