我們知道，對于一個給定的數判斷該數是不是質數，很簡單，只需要對其開根號，然后循環取模即可： public?bool?IsPrime(int?number)
????????{
????????????if?(number?<?2)
????????????{
????????????????return?true;
????????????}
????????????else
????????????{
????????????????for?(int?i?=?2;?i?<=?Math.Sqrt(number);?i++)
????????????????{
????????????????????if?(number?%?i?==?0)
????????????????????{
????????????????????????return?false;
????????????????????}
????????????????}
????????????}
????????????return?true;
????????}

?????但是，對于一個給定的整數，怎樣計算出小于該整數的所有素數呢？比較常見的是采用Sieve of Eratosthenes算法，它的基本思想是這樣：

?????由于一個合數總是可以分解成若干個質數的乘積，那么如果把質數（最初只知道2是質數）的倍數都去掉，那么剩下的就是質數了。例如要查找100以內的質數，首先2是質數，把2的倍數去掉；此時3沒有被去掉，可認為是質數，所以把3的倍數去掉；再到5，再到7，7之后呢，因為8，9，10剛才都被去掉了，而100以內的任意合數肯定都有一個因子小于10（100的開方，可參考前面判斷質數的算法），所以，去掉，2，3，5，7的倍數后剩下的都是質數了。

?????具體實現，我們通過設置兩個數組，一個bool數組crossedOut，用來標識對應下標的數字是不是質數，如果i是質數，crossedOut[i]=false，否則crossedOut[i]=true。那么劃掉i可以表示成crossedOut[i]=true。還有一個int型數組是result，用來存儲符合要求的素數。具體實現如下：

public?class?PrimeGenerator
????{
????????private?static?bool[]?crossedOut;
????????private?static?int[]?result;

????????public?static?int[]?GeneratePrimeNumbers(int?maxValue)
????????{
????????????if?(maxValue?<?2)
????????????{
????????????????return?new?int[0];
????????????}
????????????else
????????????{
????????????????UncrossIntegersUpTo(maxValue);
????????????????CrossOutMultiples();
????????????????PutUncrossedIntegersIntoResult();
????????????????return?result;
????????????}
????????}

????????private?static?void?UncrossIntegersUpTo(int?maxValue)
????????{
????????????crossedOut?=?new?bool[maxValue?+?1];
????????????for?(int?i?=?2;?i?<?crossedOut.Length;?i++)
????????????{
????????????????crossedOut[i]?=?false;
????????????}
????????}

????????private?static?void?PutUncrossedIntegersIntoResult()
????????{
????????????result?=?new?int[NumberOfUncrossedIntegers()];
????????????for?(int?j?=?0,?i?=?2;?i?<?crossedOut.Length;?i++)
????????????{
????????????????if(NotCrossed(i))
????????????????{
????????????????????result[j++]?=?i;
????????????????}
????????????}
????????}

????????private?static?int?NumberOfUncrossedIntegers()
????????{
????????????int?count?=?0;
????????????for?(int?i?=?2;?i?<?crossedOut.Length;?i++)
????????????{
????????????????if?(NotCrossed(i))
????????????????{
????????????????????count++;
????????????????}
????????????}
????????????return?count;
????????}

????????private?static?void?CrossOutMultiples()
????????{
????????????int?limit?=?DetermineIterationLimit();
????????????for?(int?i?=?2;?i?<=?limit;?i++)
????????????{
????????????????if?(NotCrossed(i))
????????????????{
????????????????????CrossOutputMultiplesOf(i);
????????????????}
????????????}
????????}

????????private?static?int?DetermineIterationLimit()
????????{
????????????double?iterationLimit?=?Math.Sqrt(crossedOut.Length);
????????????return?(int)iterationLimit;
????????}

????????private?static?void?CrossOutputMultiplesOf(int?i)
????????{
????????????for?(int?multiple?=?2?*?i;?multiple?<?crossedOut.Length;?multiple?+=?i)
????????????{
????????????????crossedOut[multiple]?=?true;
????????????}
????????}

????????private?static?bool?NotCrossed(int?i)
????????{
????????????return?crossedOut[i]?==?false;
????????}????
????}

?

轉載于:https://www.cnblogs.com/lemonade/archive/2008/12/10/1352121.html

總結

以上是生活随笔為你收集整理的找质数算法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。