减小字体
增大字体- ·上一篇文章：实现程序的唯一运行
- ·下一篇文章：试用ASP.NET实现FTP文件上传
C#实现素数的算法
在这篇文章中，我将使用C＃编制两个寻找素数的算法，说明算法设计的重要性以及算法的分析。
素数寻找问题由来已久，一直是一些数学家追求的目的。关于素数的定义及性质，我就不在这里多叙了，相信大家都对此了如指掌。素数的寻找思路比较的简单，根据素数的性质（素数应该不能被除了1和它自身的其他数整除）我们可以从最小的素数2开始，一直到比它小1的数为止，用这些数去整除它，如果它能被整除则它必定不是素数，这是判断单个素数的方法（这个算法思想最简单，时间复杂度最大）。对于寻找比某一个给定的整数值小的所有素数也可以采用这种方法，不过我们会发现，采用这种单个判断的方法所耗的时间比较多。比如查找不大于10的素数，我们必须从2开始一个个判断，共需判断9个数，事实上按照我们后面讲述的方法，只需循环2次就可以了。因此，下面的两种方法都将基于删除法来做。
我们来看看删除法的思想：
1． 将小于给定整数值n的所有正整数加到一个数组中；
2． 删除能够被一些整数整除的数；
3． 数组中遗留的元素就是最后要得到的素数序列。
对于第二步，我们将给出两种方法来实现。我们先来看看算法：
算法一：
以下内容为程序代码
这这个算法
，删除的数是那些被从2开始直到n的平方根的整数整除的数。这个算法比起前面介绍的单个素数的寻找方法要好，它的循环次数减少了一多半，但是这
素数寻找问题由来已久，一直是一些数学家追求的目的。关于素数的定义及性质，我就不在这里多叙了，相信大家都对此了如指掌。素数的寻找思路比较的简单，根据素数的性质（素数应该不能被除了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;
}
}
}
}
{
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;
}
}
}
}
这这个算法
，删除的数是那些被从2开始直到n的平方根的整数整除的数。这个算法比起前面介绍的单个素数的寻找方法要好，它的循环次数减少了一多半，但是这
