快速求1000，000范围内的所有素数，复杂度为O(n)_1000以内的素数时间复杂度为o(n)

今天收获不小啊，自创了一个快速O（n）复杂度的求1 ---- 1000，000范围内的所有素数

 

注：这个方法确实是自创，如果有人想转，请注明本文来处，否则我会很不爽的

 

思路：首先定义一个isPrime[1000001]的数组，初始化为0；isPrime[i] = 0表示i还没有确定是否是素数，isPrime[i] = 1表示i一定不是素数

 

 

            对于一个数，他一定是由某些素数相乘得到的，那么假如我们得到了一个x为素数，那么可以利用x去掉比x大的是x的倍数的数

 

           但是这样的话还是不够，因为x从2到1000，000的遍历，x的倍数也要从x往1000，000遍历，铁定不行

 

          这个时候，我们可以发现连个可以优化的地方（下面讲“判定”这个词的时候，意思就是判定是否为素数）（显然，当x遍历到一个isPrime【x】==0的时候，说明x没能被比x小的素数判定为合数，x肯定没有比x大的因子，所以x肯定是素数）

          （1），x的倍数x*y，判定x*y的时候，y不必比x小，因为如果y比x小，那么x*y一定在之前已经被判定了；如何解释：分两种情况，如果y是素数，那么x*y已经被y判定过，如果y不是素数，那么x*y一定被y的因子判定过，这时候x*y不用判定

 

          （2），x的倍数x*y，y一定不是已经被判定为isPrime【y】 = 1，即y一定不是素数，也就是说y是合数，那么这时候y的因子肯定小于或者等于x（注意有等于的情况，后面解释等于的情况要特殊处理），因为y已经被判定了，这个因子也一定是x*y的因子，那么x*y也已经被判定为不是素数了

 

          谈优化，我们可以把所有的2—1000，000用一个双向链表存起来，用where[i]表示i的链表中的节点地址，当i被判定为不是素数时就可以把i从链表中删除，利用where就可以不用遍历，O（1）的时间删除

         每次得到一个素数，遍历链表，得到判定为合数的数，删除这个数剪短链表直到这个数大于1000，000就跳出遍历，那么每遍历一个节点就删除一个节点，这个算法的复杂度可以理解为1000，000长度的链表在O（n）次的操作中遍历多少节点就删除多少节点，总的复杂度当然就是O（n）了

 

      特别注意，我们不能从素数x判定到一个数z为合数就把他从链表中删除，为什么，因为z的所有因子都是x，那么删除了z，那么z*x就没法判定了，对于这种情况，我们可以在利用了z之后删除z，而那些没法再利用的，也就是z*x大于1000，000的就直接从链表中删除

 

还有注意一点就是int溢出，所以我们可以定义一个int64的变量存相乘的值

 

模版代码：注释部分是我测试的算法复杂度，对于求1000，000以内的素数，只用了120，0000步

#include<stdio.h>
#include<string.h>
#define MAX 1000000
typedef __int64 LL;

struct List
{
 List *last;
 int value;
 List *next;
};

bool isPrime[MAX + 1];

List* where[MAX + 1];

int isResult[MAX + 1];

int init()
{
 int i;
 LL temp, temp1;
 List *p;
 List *p1;
 List *q1;
 List *head;
// int step = 0;                                              //测试用了多少步

 memset(isPrime, 0, sizeof(isPrime));

 for(i = 2; i <= MAX; i ++)
 {
  p = new List;
  where[i] = p;
  if(i == 2)
  {
   p -> last = NULL;
   p -> value = i;
   p -> next = NULL;
   head = p;
  }
  else
  {
   p -> last = where[i - 1];
   where[i - 1] -> next = p;

   p -> value = i;
   p -> next = NULL;
  }
 }

 for(i = 2; i <= MAX; i++)
 {
  if(isPrime[i])
   continue;
  else
  {
   for(p = head; p != NULL; p = p -> next)
   {
//    step ++;//测试用了多少步
    temp = i * (LL)(p -> value);
    if(isPrime[p -> value] && where[p -> value] != NULL)
    {
     temp1 = p -> value;
     p1 = where[temp1] -> last;
     q1 = where[temp1] -> next;

     p1 -> next = q1;
     if(q1 != NULL)
      q1 -> last = p1;

     delete where[temp1];
     where[temp1] = NULL;
     p = p1;
    }
    if(temp > MAX)
     break;
    if(!isPrime[temp])
    {
     isPrime[temp] = 1;
     if(temp * i > MAX)
     {
      p1 = where[temp] -> last;
      q1 = where[temp] -> next;
      delete where[temp];
      where[temp] = NULL;

      p1 -> next = q1;
      if(q1 != NULL)
       q1 -> last = p1;
     }

    }
    
   }
  }
 }

// printf("%d\n", step);//测试用了多少步

｝