素数筛选法的实现及优化

张国钦， 宋 伟， 马俊兴

(河南财政金融学院(龙子湖校区) 现代教育技术中心，河南 郑州 450046)

素数筛选法的实现及优化

张国钦， 宋 伟， 马俊兴

(河南财政金融学院(龙子湖校区) 现代教育技术中心，河南 郑州 450046)

根据素数筛选法的思想设计了一种算法，并对该算法进行了优化.对得到的算法进行了时间复杂度分析，并从平均运行时间和主要代码执行次数两个指标对算法进行度量.测试结果表明，优化后的算法具有较高的执行效率.

素数；筛选法；优化；时间复杂度；执行效率

0 引言

素数是指大于1并且只能被1和自身整除的自然数.素数在计算机中有着广泛的应用，比如用于密码设计领域的大素数，其原理是：将一个很大的数分解成若干素数的乘积非常困难，但将几个素数相乘却相对容易得多.在这种密码设计中，需要使用较大的素数，素数越大，密码被破译的可能性就越小.判断一个整数是否素数的一种简便方法是试除法[1]，求一个整数n范围内的所有素数的常用方法是古希腊数学家埃拉托色尼所发明的素数筛法[2-3].

1 素数的判断方法

1.1 基本试除法

根据素数的定义，判断一个自然数n是否为素数，可以用2～n-1之间的自然数i来除n，如果n能被i整除，则n是合数，否则n是素数.

1.2 改进的试除法

2 筛选法求素数的算法及优化

2.1 筛选法求素数的算法思想

素数筛选法的基本思想是把一定范围内的自然数中不是素数的数划去，剩下的就是素数.依据是自然数中除了1之外，不是素数，就是合数.筛选法求素数的过程描述如下：把不超过N的所有自然数按从小到大的顺序排列起来；1既不是素数，也不是合数，划去；2是素数，把2留下，再把2后面所有能被2整除的数都划去；2后面第一个没划去的数是3，把3留下，再把3后面所有能被3整除的数都划去；3后面第一个没划去的数是5，把5留下，再把5后面所有能被5整除的数都划去；这样一直做下去，就会把不超过N的全部合数都筛掉，留下的就是不超过N的全部素数.

2.2 算法实现及优化

1 #include

2 #include

3 #include

4 #define N 250000

5 int main()

6 {static int a[N+1];

7 int i,j,n=0,RepeatTimes=0;

8 long start,end;

9 start=clock();

10 for (i=1;i<=N;i++)

11 a[i]=i;

12 for (i=2;i<=sqrt(N);i++)

13 for (j=i+1;j<=N;j++)

14 {if(a[i]!=0 && a[j]!=0)

15 if (a[j]%a[i]==0)

16 a[j]=0;

17 RepeatTimes++; }

18 end=clock();

19 printf(" 求素数所用时间:time=%.3lf秒 ",(double)(end-start)/CLOCKS_PER_SEC);

20 printf("求素数执行循环次数:%d ",RepeatTimes);

21 //输出素数的代码，不是算法的主要部分，略去；

28 return 0; }

在算法a中加入了执行时间和循环次数等直观表示算法执行效率的度量指标.该算法可以进一步优化.行12的语句中函数调用sqrt(N)作为条件表达式的一部分，每次判断都要用到，因此可以把该值放在for语句之前计算出来以备调用(虽然编译器可以对此进行优化，但是我们不应该把过多的工作交给编译器去做).行14中的判断条件if(a[i]!=0 && a[j]!=0)放的位置不合适，因为如果a[i]==0即i为合数，那么i后面所有能整除i的数已经被划去了.在算法a中行8和行9之间插入“int k=sqrt(N);”，将行12至行17的代码改写如下(其他部分不变，将改写后的算法记为算法b)：

for(i=2;i<=k;i++)

if(a[i]!=0)

for (j=i+1;j<=N;j++)

{if (a[j]!=0 && (a[j]%a[i]==0))

a[j]=0;RepeatTimes++;}

for (i=2;i<=N;i++)

a[i]=1;

for(i=2;i<=k;i++)

if(a[i])

for(j=i<<1;j<=N;j+=i)

{ if(a[j])

a[j]=0;RepeatTimes++;}

2.3 算法的时间复杂度分析

3 测试结果及分析

测试机器配置为6 GB内存，处理器为Intel Celeron 2.50 GHz，操作系统为64位Windows 8.1企业版.我们指定n=250 000，3个算法分别运行10次，取平均运行时间作为算法的运行时间.测试结果如表1所示.

表1 算法测试结果

测试结果与对算法的分析基本吻合.由此可见，较好的算法优化策略能显著提高程序的执行效率.

[1] 谭浩强. C程序设计[M]. 4版.北京:清华大学出版社,2010:21.

[2] 何德彪,陈建华,胡志金. 雅克比和素性判别方法的软件实现[J]. 计算机工程与设计,2007,28(16):3818-3821.

[3] 张琦,许勇. Matlab环境下素数筛选算法的分析及比较[J]. 计算机技术与发展,2009,19(3):95-98.

[4] GRAHAM R L,KNUTH D E,PATASHNIK O．具体数学:计算机科学基础[M].张明尧,张凡，译. 2版. 北京:人民邮电出版社,2013:376.

[5] CORMEN T H,LEISERSON C E,RIVEST R L, et al．算法导论[M].殷建平,徐云，王刚,等,译. 3版. 北京:机械工业出版社,2013:565.

Implementation and Optimization of Prime Sieve Method

ZHANG Guoqin, SONG Wei, MA Junxing

(CenterofModernEducationalTechnology,HenanInstituteofFinanceandBanking(LongzihuCampus),Zhengzhou450046,China)

An algorithm is designed according to the idea of prime sieve method, and it is optimized. The time complexity of the algorithm is analyzed, and the algorithm is measured by two indexes: the average running time and the main code execution times. The test results show that the optimized algorithm has high execution efficiency.

prime number; sieve method; optimization; time complexity; execution efficiency

2017-01-19

河南省高等学校重点科研项目计划(16A520008)

张国钦(1975—)，男，河南南阳人，河南财政金融学院(龙子湖校区)现代教育技术中心工程师.

10.3969/j.issn.1007-0834.2017.01.008

TP311.1

A

1007-0834(2017)01-0039-03