篩法求質數------------2012年12月30日

       問題描述:使用篩法求質數。有一個很神奇的篩子，可以給它一個數i，這個篩子有辦法把i的所有倍數去掉。請用這個方法求出2到N之間的所有質數。要求，程式不能使用乘法和除法，隻能用加或減，以求加快速度。

        該問題的思路來自《C語言名題精選百則技巧篇》，很慚愧，我對這樣的涉及一些數學知識的題很少有解決的辦法，我需要在這一方面加強。

        我把書中的思路歸納如下，并加上了我自己的一些想法。

        1.   2的倍數都不是質數，是以不比考慮2的倍數。2是質數，是以考慮的數的集合是   2i+3,i=0,1,2,3,4.......

        2.   求質數，隻需要處理到num/2就可以了。在程式中MAX為基準，算出2到2*MAX+3之間的質數，實際也是處理到MAX就停止了。

        3.   程式不能使用乘法，隻能使用加法和減法，是以就需要作一些數學方面的處理:2i+3是一個奇數，要去除它的倍數。在第1點中，已經去除了2的倍數，是以就不用管2i+3的偶數倍的數了，隻需要處理2i+3的奇數倍的數了。是以，我們需要去除(2n+1)(2i+3),n=1,1,2,3,4....當然，不能去除2i+3本身。然後對(2n+1)(2i+3)做一個變形，朝着2N+3這樣的形式去變形(ps:這是我以前在數學證明題中經常做的)。變形過程:(2n+1)(2i+3)=2n(2i+3)+2i+3=2[n(2i+3)+i]+3;這就是2N+3的形式了(N就是n(2i+3)+i)。由于在程式中我們是以i作為索引的，是以我們用篩子篩出為止為N的數，也就是删除位置為n(2i+3)+i的數。這樣，就不難寫出程式了。

        代碼如下:

        總結:與一些數學變換相結合的程式題是我的一個弱項，自己總是想不到這樣的想法，最根本的原因就是這樣思考得太少了以及數學功底不夠。在以後需要多加強數學知識的學習以及數學與程式相結合的算法(資料結構)甚至是項目實踐等等練習。 

本文轉自NeilHappy 51CTO部落格，原文連結：http://blog.51cto.com/neilhappy/1104740，如需轉載請自行聯系原作者