今天收獲不小啊，自創了一個快速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);//測試用了多少步
｝
