線性篩法求素數

2022-11-24 17:06:18 字數 2704 閱讀 5473

題目:給出一個正整數n,列印出所有從1~n的素數(即質數);

關鍵是要找出一個判斷一個正整數n是否為素數的方法...

傻瓜解法--n,n/2

1 #include2

intmain()

3 11 }

這是理所當然的想法,按照素數的定義,除了1和它本身沒有其他的因數,就是素數。

這種解法的缺點就是紅色標註那裡,i普通解法--sqrt(n)

1 #include2 #include3

intmain()

4 12 }

這裡迴圈取到sqrt(n),效率改進不少了...但顯然還是不夠理想....繼續往下看

普通篩選法--埃拉託斯特尼篩法

先簡單說一下原理:

基本思想:素數的倍數一定不是素數

實現方法:用一個長度為n+1的陣列儲存資訊(0表示素數,1表示非素數),先假設所有的數都是素數(初始化為0),從第一個素數2開始,把2的倍數都標記為非素數(置為1),一直到大於n;然後進行下一趟,找到2後面的下一個素數3,進行同樣的處理,直到最後,陣列中依然為0的數即為素數。

說明:整數1特殊處理即可。

舉個例子,n=20時,演示如下圖:

最後陣列裡面還是0的就是素數了...

**實現如下:

prime用來儲存得到的素數 prime = tot 是當前得到的素數的個數 check :0表示是素數  1表示合數

1 memset(check, 0, sizeof

(check));

2int tot = 0;3

for (int i = 2; i <= n; ++i)49

for (int j = i+i; j <= n; j +=i)

1013 }

此篩選法的時間複雜度是o(nloglogn) 空間複雜度是o(n)

不足之處也比較明顯,手動模擬一遍就會發現,很多數被處理了不止1遍,比如6,在素數為2的時候處理1次,為3時候又標記一次,因此又造成了比較大的不必要處理...那有沒有改進的辦法呢...就是下面改進之後的篩法...

線性篩法--尤拉篩法

先上**吧...

1 #include2 #include3

#define maxn 100005

4#define maxl 1299710

5int

prime[maxn];

6int

check[maxl];78

int tot = 0

;9 memset(check, 0, sizeof

(check));

10for (int i = 2; i < maxl; ++i)

1116

for (int j = 0; j < tot; ++j)

1722 check[i*prime[j]] = 1;23

if (i % prime[j] == 0)

2427

}28 }

精華就在於紅色標註那兩處,它們保證每個合數只會被它的最小質因數篩去,因此每個數只會被標記一次,所以時間複雜度是o(n)

還是按上面的例子進行一遍模擬:n=20

此過程中保證了兩點:

1、合數一定被幹掉了...

2、每個數都沒有被重複地刪掉

(證明 見參考資料)

引申--求尤拉函式

在數論,對正整數n,尤拉函式是小於或等於n的數中與n互質的數的數目。此函式以其首名研究者尤拉命名,它又稱為euler's totient function、φ函式、尤拉商數等。 例如φ(8)=4,因為1,3,5,7均和8互質。

求尤拉函式的方法只需在上面的程式中稍有改動即可,此處只貼出**:

1 #include2 #include3

#define maxn 100005

4#define maxl 1299710

5int

prime[maxn];

6int

check[maxl];

7int

phi[maxl];

8int tot = 0

;9 phi[1] = 1

;10 memset(check, 0, sizeof

(check));

11for (int i = 2; i < maxl; ++i)

1218

for (int j = 0; j < tot; ++j)

1924 check[i*prime[j]] = 1;25

if (i % prime[j] == 0)26

else

3033

}34 }

若是素數,那麼從1~n-1都是和它互質的數,所以phi(i) = i - 1;

另外兩個是積性函式(見參考資料)的公式和尤拉函式的特性。

參考資料

1、2、

3、

牛頓法求 方根

世界,早安!這幾個晚上經常睡不著,12點多上去睡覺到3點才能睡去,所以昨晚決定拿本無聊的書去看,看到無聊之處自然就睡著了 然後找了本 計算機程式的構造和解釋 第二版 是在上推薦的。翻看了幾頁,發現了一種叫求 方根的牛頓法 牛頓真的是無處不在呀 你任說1個整數x,我任猜它的 方根為y,如果不對或精度不...

篩法求素數

要解決的問題 給定一個正整數 n 求出所有小於等於 n 的素數 素數又稱質數,其因子只有1和它自己本身 與素數相對的叫合數 includeusing namespace std define n 10000 define ll long long int visited n int prime n ...

c 冪法求特徵向量

冪法的原理可參考此篇 本文求解的是 3 階矩陣最大特徵值及其特徵向量 下面是其 c 實現 include include include include includeusing namespace std double a 3 3 double y 3 double x 3 int row 0 i...