WEB开发网
开发学院软件开发数据结构 C#算法设计与分析-寻找素数 阅读

C#算法设计与分析-寻找素数

 2009-10-09 11:57:49 来源:WEB开发网   
核心提示:素数寻找问题由来已久,一直是一些数学家追求的目的,C#算法设计与分析-寻找素数,关于素数的定义及性质,我就不在这里多叙了,我们来看看删除法的思想:1.将小于给定整数值n的所有正整数加到一个数组中;2.删除能够被一些整数整除的数;3.数组中遗留的元素就是最后要得到的素数序列,对于第二步,相信大家都对此了如指掌,素数的寻找

素数寻找问题由来已久,一直是一些数学家追求的目的。关于素数的定义及性质,我就不在这里多叙了,相信大家都对此了如指掌。素数的寻找思路比较的简单,根据素数的性质(素数应该不能被除了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;
          }         
       }
     }
   }

1 2  下一页

Tags:算法 设计 分析

编辑录入:爽爽 [复制链接] [打 印]
赞助商链接