C＃算法設計與分析－尋找素數（1）

數尋找問題由來已久，一直是一些數學家追求的目的。關於素數的定義及性質，我就不在這裡多敘了，相信大家都對此了如指掌。素數的尋找思路比較的簡單，根據素數的性質（素數應該不能被除了1和它自身的其他數整除）我們可以從最小的素數2開始，一直到比它小1的數為止，用這些數去整除它，如果它能被整除則它必定不是素數，這是判斷單個素數的方法（這個算法思想最簡單，時間復雜度最大）。對於尋找比某一個給定的整數值小的所有素數也可以采用這種方法，不過我們會發現，采用這種單個判斷的方法所耗的時間比較多。比如查找不大於10的素數，我們必須從2開始一個個判斷，共需判斷9個數，事實上按照我們後面講述的方法，只需循環2次就可以了。因此，下面的兩種方法都將基於刪除法來做。

我們來看看刪除法的思想：

1．將小於給定整數值n的所有正整數加到一個數組中；

2．刪除能夠被一些整數整除的數；

3．數組中遺留的元素就是最後要得到的素數序列。

對於第二步，我們將給出兩種方法來實現。我們先來看看算法：

算法一：

class prime
　　 {
　　　　 public static int[] PrimeList;
　　　　 public　static void FindPrime(int n)
　　　　 {
　　　　　　　int[] IntList;
　　　　　　　IntList=new int[n];　　　　　　　
　　　　　　　for (int p=2;p<=n;p++) IntList[p-1]=p;
　　　　　　　for (int p=2;p<Math.Sqrt(n);p++)
　　　　　　　{
　　　　　　　　　 int j=p+1;
　　　　　　　　　 while (j<=n)
　　　　　　　　　 {
　　　　　　　　　　　 if ((IntList[j-1]!=0 ) && ((IntList[j-1]% p)==0) ) IntList[j-1]=0;
　　　　　　　　　　　 j=j+1;
　　　　　　　　　 }
　　　　　　　}
　　　　　　　int i=0;
　　　　　　　for (int p=2;p<=n;p++)
　　　　　　　{
　　　　　　　　　 if (IntList[p-1]!=0) i=i+1;
　　　　　　　}
　　　　　　　PrimeList=new int[i];
　　　　　　　i=0;
　　　　　　　for (int p=2;p<=n;p++)
　　　　　　　{
　　　　　　　　　 if (IntList[p-1]!=0)
　　　　　　　　　 {
　　　　　　　　　　　 PrimeList[i]=IntList[p-1];
　　　　　　　　　　　 i=i+1;
　　　　　　　　　 }　　　　　　　　　
　　　　　　　}
　　　　 }
　　 }