天天看點

CSP-J初賽知識點 一篇文章徹底搞懂線性篩(素數篩)

基礎

我們不着急開始線性篩隻的證明,從基礎開始,先來了解一下什麼是素數,什麼是合數。

合數和因數

假定有一個數x,它能被兩個數相乘表達出來,即a*b=x,而且這個a、b都不為0,那麼這個數x就是合數,與此同時a、b就是它的兩個因數

素數

假定有一個數x,它隻能被1和它本身相乘所表示,那麼這個數就是素數。

由此,我們知道了一個概念:自然數的集合是由素數和合數兩種數組合起來的。

質因數

既是質數也是因數的數就是質因數。

例如,5是一個質數,同時也是25的因數,那麼這個數也就是25的一個質因數。

整除

除法都會吧?

如果有a*b=c,我們就稱c能夠整除a或者c能夠整除b。我們記作clb或者cla。記住上面的基礎知識,這對于你接下來對每個方法的了解很重要!接下來我們從暴力破解到一點點的優化到素數篩的發展逐一的介紹:

暴力求解

想要判斷一個數是不是素數,從他的定義入手:

假定有一個數x,它隻能被1和它本身相所表示,那麼這個數就是素數。

我們就看看它有沒有除了1和它本身之外的因數呗,直接循環周遊比他小的所有值就可以了:

CSP-J初賽知識點 一篇文章徹底搞懂線性篩(素數篩)
CSP-J初賽知識點 一篇文章徹底搞懂線性篩(素數篩)

這就是最簡單的暴力破解算法,對于每一個數我們都去尋找比他小的"可能存在的因數”,當然,你也可以發現:偶數一定不是素數的,1、11一定都是素數,基于此你也可以産生很多優化:但是今天的主題并不是這個,再此就不細究。

CSP-J初賽知識點 一篇文章徹底搞懂線性篩(素數篩)

真正的篩--埃式篩

普通的暴力破解有個特點:

我們一直在關注素數的特性,想着如何去将素數找出來,但是卻忽略了合數,

假設我們将所有的合數都進行标記,那剩下的數不就都是素數了嗎?

根據合數的定義我們知道:合數一定存在不為1和它本身的因數,那麼假設有一個質數q,那麼2q,3q,4q...一定是合數呀!

基于此,真正的篩,誕生了!

我們觀察自然數,0和1不去考慮,他們本身就不是合數,那麼2是一個素數,既然這樣,我們就把2的倍數全部标記!這些數都是合數!

之後發現3是素數,那麼3的所有倍數也都是合數!繼續标記!

如何用代碼來表示我們的想法呢?

我們可以開辟一塊足夠大的空間,也就是一個數組,這個數組各部分的語義如下:

1. 下标:表示每一個數字,

2. 存儲内容:表示對應下标數字的狀态,也就是說是否為素數

接下來舉個例子:

假如我們想要輸出100之前的所有素數,我們的數組就要大于100,初始時每個存儲空間存儲的都為0,表示我們假定所有數都是素數(就像一個篩糠的過程,一開始糠全部在篩子上面)。

然後依次周遊每一個值,從2開始,我們發現2是素數,那麼接下來我們就取循環标記數組中下标為2的倍數的值,将他們存儲的空間中記為1,表示他們為合數。

周遊到3,繼續去标記3的倍數,以此類推….

代碼如下:

CSP-J初賽知識點 一篇文章徹底搞懂線性篩(素數篩)
CSP-J初賽知識點 一篇文章徹底搞懂線性篩(素數篩)

我們會發現一個問題:

當i=2 => 2i=4,3i=6,4i=8.

當i=3 => 2i=6,3i=9,4i=12.

當i=4 => 2i=8...

發現了嗎?我們似乎重複标記了一些數字,那該怎麼解決這個問題呢?接下來就是埃式篩的更新版,也是最終版--線性篩:

線性篩

我們來分析一下重複标記的原因:在上面的埃式篩中,當我們遇到素數後,将它的倍數全部标記,由此可以推斷:一個數被重複标記的原因是因為它有不同質數的因數。

也就是說,我們使用了多個質因數去标記了這個合數。

例如:

12被2和3标記過,30被2、3、5同時标記過。

分析出了原因,優化方向就呼之欲出了:

我們隻要使用最小質因數去标記這個數(十分重要,這是線性篩的核心原理所在)就行了,具體該怎麼做呢?具體來說就是維護一個标記數組 a 和一個已有素數數組 pimes ,然後,我們從2開始周遊所有數ì,并目:(接下來這兩條好好了解!!核心部分!!)

①把遇到所有未被标記,為質數的數i(埃式篩中從小到大周遊時遇到的一個個質數)存到 primes 裡去;

②以i為第一個因子,分别以 primes 裡每個質數j為第二個因子,求積,可以斷定ì必為合數,故标記之;同時,若 mod(i,j)==0,說明j是i的一個質因數,又因為 primes 數組中的元素是遞增的,j是第一個可以除斷ì的,故可斷定j是i的最小質因數,同時也是i.j的最小質因數,那麼更進一步也可斷定j 之後的質數"一定不是 i* 的最小質因數,故結束 primes 的周遊。

CSP-J初賽知識點 一篇文章徹底搞懂線性篩(素數篩)
CSP-J初賽知識點 一篇文章徹底搞懂線性篩(素數篩)

這個圖檔說明了線性篩的執行過程(從左到右從上到下)

紅色是被優化的部分。

為了幫助了解,我們根據代碼過程和前幾個數進行一下過程模拟:

CSP-J初賽知識點 一篇文章徹底搞懂線性篩(素數篩)
CSP-J初賽知識點 一篇文章徹底搞懂線性篩(素數篩)

綜上就是線性篩的算法邏輯,為證明它需要考慮的出乎意料地多,了解"(%primers[]==0)break;"語句也才僅僅是了解皮毛(值得一提的是,即使删去此語句,餘下的部分也是相當優秀的程式)。

CSP-J初賽知識點 一篇文章徹底搞懂線性篩(素數篩)

繼續閱讀