求素数列表和判断素数的算法

1、求素数列表和判断素数的算法有兴趣阅读本文的读者，应该对素数概念是十分熟悉的了。用计算机程序实现素数计 算，集中在2个主要问题上：判断一个正整数是否是素数-(算法A)*求一定范围内的素数列表-(算法B)关于素数的算法，根据素数的数学性质，大家都会想到如下几个方面：*用遍历求模的方式判断素数 素数都是奇数，可以在奇数数列中寻找素数*利用开方来缩小搜索的范围然后，求素数的计算是复杂的，如果算法写得不好，则耗时较高。在百度百科“素数”条目中的算法程序，是值得商榷的。很多方法是O(N2 )的算法。为此，在本文中探讨了求素数列表和判断素数这两个算法，力图使算法可以达到O(N Log(N)优化级别。在本文中

2、，算法语言选用C#。1,判断素数的简单实现(算法 A-1)/ / 算法A-1，判断素数/ |/ vparam name=number 待测正整数 / 是否为素数(为了简化，1以下的整数皆为素数) public static bool lsPrime( int number)/为了简化，1以下的整数皆为素数if (number = 2) I二return true ;/奇偶性if (number % 2 = 0)return false ;/利用开方缩小范围，优化效果十分明显int range = ( int ) Math .Sqrt(number) + 1;/从3开始的奇数列for ( int

3、 current = 3; current = range; current += 2)/判断是否为素数if (n umber % curre nt = 0)/合数return falsereturn true ;A-1算法中，首先判断奇偶性，再判断从3开始判断待查数(number)是否是合数，若到Math.Sqrt(number)还没有查到是合数，即为素数。这个方法是0(N1/2)级别的算法，所以很快，即使是最悲观的int.MaxValue，在本人的本机计算也可达到125ms的运行时间。2,判断素数的优化算法(A-2)虽然这种算法速度比较快，但如果频繁使用A-1算法，累计起来开销就比较大了，

4、假设有N次访问的话，算法级别就到了O(N3/2)。因此，本人的解决方案是先计算出一定范围内的素数列表存放在哈希表中，多次调用 就可以忽略查询时间了。/|/ 素数的Hash表/ private static HashSet Primes get ; set ; /算法A-2，判断素数/ |/ 待测正整数 / 是否为素数(为了简化，1以下的整数皆为素数)public staticbool lsPrime2( int number)/为了简化，1以下的整数皆为素数if (number = 2) 1return true ;returnPrimes.C on tai ns(n umber);这种算法的

5、前提是要求一个素数表，这就是算法B要研究的问题了3求素数列表的简单算法(B-1)/ /求素数列表的简单算法(算法B-1)/ / /public static int GetPrimes( int range)List primeList = new List ();/从3开始的奇数列for (int current = 3; current = range; current += 2)/判断是否为素数bool isPrime = true ;foreach ( int prime in primeList)isPrime =if (isPrime)/加入素数列表primeList.Add(cu

6、rre nt);/把2补入primeList. In sert(0, 2);return primeList.ToArray();上述算法，是对小于 并加入素数表。N的数，遍历素数表，判断是否为合数，全不成立的即为素数,这个算法的一个特点是只对奇数数列进行遍历，从而使遍历次数减少了一半。4,步长优化的算法（算法B-2）有读者会想到阴阳素数数列的问题，也就是除了2,3以外，素数要么在（6N-1）数列,要么在（6N+1）数列，这样，是不是就可以通过改变步长方式就可以提高速度？是的，本人也做过这样的实验，代码如下：/ /求素数列表的简单算法(算法B-2)/ |/vparam n ame=ra nge

7、/vretur nspublic static int GetPrimes2( int range)List primeList = new List ();步长int index = 1; /步长下标int loops = new int 2, 4 ;/ for ( int current = 5; current = maxValue; current += loopsindex)/判断是否为素数bool isPrime = true ;foreach ( int prime in primeList)if (current % prime = 0)/若为合数，进入下一数的判断isPrim

8、e =false ;break ;if (isPrime)/加入素数列表primeList.Add(curre nt);in dex A= 1; /阴阳数列转换/ 把2，3补入primeList. In sert(0, 2);primeList.Insert(0, 3);return primeList.ToArray();采用步长数组和异或操作切换，可以最大限度的不增加代码优化后的开销。这样的优化取得了一定的优化效果，但效果不明显。我分析，B-1是最多达到了 50%的优化，而B-2是达到了 33.3%的优化效果，所以优化不明显。所以后面的算法，就忽略了B-2的这样的优化。5，采用开方法优化的

9、算法(算法-B-3)本文的重点来了求素数列表的一大挑战，是当求解的范围很大时，速度就会变得其慢。在对int.MaxValue/ 10000规模计算中，大致是 1910ms左右，在往上速度就很慢了。分析原因，算法中的最大的瓶颈在于求模操作。由于求模操作命中率不高，所以执行 次数很多。根据数论知识，可以得到下来推论：把全集 X = n|n = N,可以分为两个子集， X仁n | n = N1/2 + 1和X2=n | N1/2 + 1 n =N, Y1是X1中的素数子集，丫2是X2中的素数子集，则 X2中的所有合数的因数，全 属于Y1。(推论-1)B-1方法求1到N1/2 + 1部分的这个推论告诉

10、我们，我们可以把算法分成两部分，按Y2,素数(Y1),在把N1/2 + 1到N的数求模一次求素数(而不是遍历素数表)，得到 Y1+Y2就是全部素数表。/|/ 平方法(算法B-3)/ /public static int GetPrimes3( int maxValue)int range = ( int ) Math.Sqrt(maxValue);/素数列表List primeList = new List ();int curre nt = 3;/从3开始的奇数列for (; current = range; current += 2)/判断是否为素数bool isPrime = true

11、; foreach ( int prime in primeList)if (current % prime = 0)/若为合数，进入下一数的判断isPrime =false ;break ;if (isPrime)/加入素数列表primeList.Add(curre nt);List primeList2 = new List ();/从3开始的奇数列for (; current = maxValue; current += 2)/判断是否为素数bool isPrime = true ; foreach ( int prime in primeList) if (current % prim

12、e = 0)/若为合数，进入下一数的判断isPrime =false ;break ; if (isPrime)/加入素数列表primeList2.Add(curre nt);/把2补入primeList. In sert(0, 2); primeList.AddRa nge(primeList2);return primeList.ToArray();这样的修改将使运行效率提高了近100倍6,利用筛法进行更高级的优化(算法B-4)对于上述用例，主要对 19980个素数的二次循环上，在从N1/2到N之间的数中，进行log(M1)的循环(基数是623)和求模。所以这个算法的复杂度是 O(log(

13、M1)*(N- N1/2)我们继续把范围划分 3段(X1, X2, X3)为3到N1/4，N1/4到N1/2，N1/2到N 部分，素数集分别是 Y1, Y2, Y3,这样就可以把循环的基数变得更小了。还有什么可以优化的？这是我考虑到了筛法。区域范围全集素数集合数集13N1/4X1Y1-2N1/4N1/2X2Y2-3N1/2NX3Y3Z30,含有Y1的因数Z31,Y2中的2个素数的积Z32,Y2中的3个素数的积Z33,一个Y2中的素数和一个 Y3中的积我们注意到X3部分的合数集有4个真子集:* Z30,含有Y1的因数，用Y1素数集简单遍历可以判断是合数；* 只要得岀丫2,就可以得岀Z31和Z32

14、,并加入到一个 Hashtable 中。* 遍历X3时，先判断是不是属于 Z31和Z32的合数，再判断是否是 Z30的合数，剩下的就是 Y3 的一个素数。* 再对这个与丫2的所有元素相乘后的积，就是Z33合数集的一个元素，也加入这个Hashtable* 最后就得到了这个素数集。public static int GetPrimes4( int maxValue)/素数列表List primeList = new List ();int range1 = ( int ) Math .Sqrt( Math .Sqrt(maxValue) + 1;int range2 = ( int ) Math

15、.Sqrt(maxValue) + 1;int curre nt = 3;/从3开始的奇数列(丫1)for (; curre nt = ran gel; curre nt += 2)/判断是否为素数if (lsPrime(curre nt, primeList)/加入素数列表primeList.Add(curre nt);/第二部分素数表(丫2)List primeList2 = new List ();for (; current = range2; current += 2)/判断是否为素数if (IsPrime(curre nt, primeList)HashSet compositer

16、Map = new HashSet ();/ 合数 Hash表(Z31,Z32)var primeArray2 = primeList2.ToArray();var primeLength2 = primeList2.Count();for (int i = 0; i primeLength2; i+)for (int j = i; j primeLength2; j+ )int prime3 = primeArray2i * primeArray2j;compositerMap.Add(prime3);/ 第 1 类合数for ( int k = j; k primeLength2; k+)

17、long prime4 = ( long )prime3 * primeArray2k;if (prime4 = maxValue)compositerMap.Add(int )prime4);/ 第2类合数1 ,elsebreak ; /第三部分素数表List primeList3 = new List (); for (; current = maxValue; current += 2)/筛除已知合数if (compositerMap.C on tai ns(curre nt)con ti nue ;/判断是否是素数(只需判断第一素数集即可)(Z30合数集)if (IsPrime(cur

18、re nt, primeList)/加入素数列表primeList3.Add(curre nt);/添加第3类合数for ( int j = 0; j primeLength2; j+)long newPrime = ( long )current * primeArray2j;if (newPrime = maxValue) compositerMap.Add(int )newPrime); / 第3类合数(Z33合数集)e sebreak ;/把2补入primeList. In sert(0, 2);return primeList.U nio n(primeList2).U nion (primeList3).ToArray();这部分的代码的亮点，是对 Z31,Z32,Z33 的合数进行Hashtable的筛除，而Z30的进行少数几个循环 求模操作，从而会提高很大的效率。有读者会问，这个算法用素数的乘法代替了数的取模，值得吗？回答是肯定的。假设用B-3的方法，X3区域的所有素数将被遍历所有 丫1, Y2的素数，而丫2的素数有好几百个，X3的遍历是很大的；对所有 样本数的计算都会用到多次的取模，数