C＃算法設(shè)計(jì)與區(qū)分－尋找素?cái)?shù)
發(fā)表時(shí)間：2024-01-16 來(lái)源：明輝站整理相關(guān)軟件相關(guān)文章人氣：
[摘要]在這篇文章中，我將使用C＃編制兩個(gè)尋找素?cái)?shù)的算法，說(shuō)明算法設(shè)計(jì)的重要性以及算法的分析。 素?cái)?shù)尋找問(wèn)題由來(lái)已久，一直是一些數(shù)學(xué)家追求的目的。關(guān)于素?cái)?shù)的定義及性質(zhì)，我就不在這里多敘了，相信大家都對(duì)此了如指掌。素?cái)?shù)的尋找思路比較的簡(jiǎn)單，根據(jù)素?cái)?shù)的性質(zhì)（素?cái)?shù)應(yīng)該不能被除了1和它自身的其他數(shù)整除...
在這篇文章中，我將使用C＃編制兩個(gè)尋找素?cái)?shù)的算法，說(shuō)明算法設(shè)計(jì)的重要性以及算法的分析。
素?cái)?shù)尋找問(wèn)題由來(lái)已久，一直是一些數(shù)學(xué)家追求的目的。關(guān)于素?cái)?shù)的定義及性質(zhì)，我就不在這里多敘了，相信大家都對(duì)此了如指掌。素?cái)?shù)的尋找思路比較的簡(jiǎn)單，根據(jù)素?cái)?shù)的性質(zhì)（素?cái)?shù)應(yīng)該不能被除了1和它自身的其他數(shù)整除）我們可以從最小的素?cái)?shù)2開(kāi)始，一直到比它小1的數(shù)為止，用這些數(shù)去整除它，如果它能被整除則它必定不是素?cái)?shù)，這是判斷單個(gè)素?cái)?shù)的方法（這個(gè)算法思想最簡(jiǎn)單，時(shí)間復(fù)雜度最大）。對(duì)于尋找比某一個(gè)給定的整數(shù)值小的所有素?cái)?shù)也可以采用這種方法，不過(guò)我們會(huì)發(fā)現(xiàn)，采用這種單個(gè)判斷的方法所耗的時(shí)間比較多。比如查找不大于10的素?cái)?shù)，我們必須從2開(kāi)始一個(gè)個(gè)判斷，共需判斷9個(gè)數(shù)，事實(shí)上按照我們后面講述的方法，只需循環(huán)2次就可以了。因此，下面的兩種方法都將基于刪除法來(lái)做。
我們來(lái)看看刪除法的思想：
1． 將小于給定整數(shù)值n的所有正整數(shù)加到一個(gè)數(shù)組中；
2． 刪除能夠被一些整數(shù)整除的數(shù)；
3． 數(shù)組中遺留的元素就是最后要得到的素?cái)?shù)序列。
對(duì)于第二步，我們將給出兩種方法來(lái)實(shí)現(xiàn)。我們先來(lái)看看算法：
算法一：
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;
}
}
}
}
這這個(gè)算法中，刪除的數(shù)是那些被從2開(kāi)始直到n的平方根的整數(shù)整除的數(shù)。這個(gè)算法比起前面介紹的單個(gè)素?cái)?shù)的尋找方法要好，它的循環(huán)次數(shù)減少了一多半，但是這個(gè)算法還不是最理想的：
1． 例如，6既能被2整除，也能被3整除，那么當(dāng)p＝2時(shí)，6被刪掉了一次；當(dāng)p＝3時(shí)，6又被刪除了一次，雖然按照我們?cè)O(shè)定的算法規(guī)則，這不會(huì)導(dǎo)致沖突（通過(guò)判斷IntList數(shù)組元素是否為0，若為0就不必重復(fù)刪除），但是這會(huì)使得算法的效率低下。
2． 還有計(jì)算素?cái)?shù)序列元素個(gè)數(shù)時(shí)，我們也走了彎路。第一步，我們先計(jì)算出了數(shù)組元素大小，第二步才開(kāi)始賦值，事實(shí)上這兩步我們可以減去計(jì)算數(shù)組大小這一步，可以把它放在前面完成。
3． 已經(jīng)被刪除了的元素，也就是那些不是素?cái)?shù)的元素，可以不用拿他們?nèi)フ麛?shù)，例如4不用拿去整除8，因?yàn)槟鼙?整除的數(shù)肯定能被2整除，已經(jīng)在前面循環(huán)中被刪除了。
基于上述考慮，我們得到了一個(gè)效率更加高的算法：
class primegood
{
public static int[] PrimeList;
public static void FindPrime(int n)
{
int[] IntList;
int len=n-1;
IntList=new int[n];
for (int p=2;p<=n;p++) IntList[p-1]=p;
for (int p=2;p<Math.Sqrt(n);p++)
{
if (IntList[p-1]==0) continue;
int j=p*p;
while (j<=n)
{
if (IntList[j-1]!=0 )
{
IntList[j-1]=0;
len=len-1;
}
j=j+p;
}
}
PrimeList=new int[len];
int i=0;
for (int p=2;p<=n;p++)
{
if (IntList[p-1]!=0)
{
PrimeList[i]=IntList[p-1];
i=i+1;
}
}
}
}
這個(gè)算法思想和前面的算法完全一樣，不過(guò)改正了上面算法中不完善的一些內(nèi)容。
為了說(shuō)明這兩個(gè)算法的效率區(qū)別，我們編制了如下的主程序來(lái)比較一下他們的差異：
static void Main()
{
Console.WriteLine("Start!");
DateTime mytime5=DateTime.Now;
primegood.FindPrime(100000);
/*for (int i=0;i<=primegood.PrimeList.Length-1;i++)
{
Console.WriteLine(primegood.PrimeList[i]);
}*/
DateTime mytime6=DateTime.Now;
TimeSpan timeadd3=mytime6-mytime5;
Console.WriteLine(timeadd3.Ticks);
DateTime mytime1=DateTime.Now;
prime.FindPrime(100000);
DateTime mytime2=DateTime.Now;
TimeSpan timeadd=mytime2-mytime1;
DateTime mytime3=DateTime.Now;
primegood.FindPrime(100000);
DateTime mytime4=DateTime.Now;
TimeSpan timeadd2=mytime4-mytime3;
Console.WriteLine(timeadd.Ticks);
Console.WriteLine(timeadd2.Ticks);
}
}
通過(guò)運(yùn)行這個(gè)程序，可以發(fā)現(xiàn)他們的差別是如此的大（前面的算法所耗時(shí)間幾乎是后面算法的30－60倍），參見(jiàn)下圖：
事實(shí)上，這兩個(gè)算法的時(shí)間復(fù)雜度近似為：⊙（n1.5）；⊙（n）；可見(jiàn)，對(duì)于同一個(gè)問(wèn)題有著多種不同復(fù)雜性的算法實(shí)現(xiàn)，算法設(shè)計(jì)是一門(mén)十分重要的學(xué)問(wèn)。
