2016.1.25
我們都知道，判斷一個數是否為素數可以在O(√n)的時間復雜度內解決。但是如果是要求[1,n]內素數的個數，顯然一個一個判斷有些慢了。
但我們知道一個顯而易見的性質：一個合數的所有質因數都小於這個合數，一個質數沒有比它小的質因數。
那麼我們可以利用已求得的質因數，來對比他大的合數進行篩除。
具體操作如下：首先我們將2至n內的所有數字寫下來。此時2為表中最小數，即為素數，然後將2的倍數全部劃去。此時表中剩余最小數字是3，即3是素數，再將表中所有3的倍數劃去。將該操作進行下去，每次表中剩余的最小的數即為素數，並將它的倍數都劃去。
