基礎
我們不着急開始線性篩隻的證明，從基礎開始，先來了解一下什麼是素數，什麼是合數。
合數和因數
假定有一個數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和它本身之外的因數呗，直接循環周遊比他小的所有值就可以了:
這就是最簡單的暴力破解算法，對于每一個數我們都去尋找比他小的"可能存在的因數”，當然，你也可以發現:偶數一定不是素數的,1、11一定都是素數，基于此你也可以産生很多優化:但是今天的主題并不是這個，再此就不細究。
真正的篩--埃式篩
普通的暴力破解有個特點:
我們一直在關注素數的特性，想着如何去将素數找出來，但是卻忽略了合數，
假設我們将所有的合數都進行标記，那剩下的數不就都是素數了嗎?
根據合數的定義我們知道:合數一定存在不為1和它本身的因數，那麼假設有一個質數q，那麼2q，3q，4q...一定是合數呀!
基于此，真正的篩，誕生了!
我們觀察自然數，0和1不去考慮，他們本身就不是合數，那麼2是一個素數，既然這樣，我們就把2的倍數全部标記!這些數都是合數!
之後發現3是素數，那麼3的所有倍數也都是合數!繼續标記!
如何用代碼來表示我們的想法呢?
我們可以開辟一塊足夠大的空間，也就是一個數組，這個數組各部分的語義如下:
1. 下标:表示每一個數字，
2. 存儲内容:表示對應下标數字的狀态，也就是說是否為素數
接下來舉個例子:
假如我們想要輸出100之前的所有素數，我們的數組就要大于100，初始時每個存儲空間存儲的都為0，表示我們假定所有數都是素數(就像一個篩糠的過程，一開始糠全部在篩子上面)。
然後依次周遊每一個值，從2開始，我們發現2是素數，那麼接下來我們就取循環标記數組中下标為2的倍數的值，将他們存儲的空間中記為1，表示他們為合數。
周遊到3，繼續去标記3的倍數，以此類推….
代碼如下:
我們會發現一個問題:
當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 的周遊。
這個圖檔說明了線性篩的執行過程(從左到右從上到下)
紅色是被優化的部分。
為了幫助了解，我們根據代碼過程和前幾個數進行一下過程模拟:
綜上就是線性篩的算法邏輯，為證明它需要考慮的出乎意料地多，了解"(%primers[]==0)break;"語句也才僅僅是了解皮毛(值得一提的是，即使删去此語句，餘下的部分也是相當優秀的程式)。