第 1 .第期 9巷
20 0 9年 3月
.
计算机技术与发展
(( M It ER E(HN( L : ANI、 ) 门。 F 7 ) ( Y )DEVEI I l:』) FNT
V( .9 No. ) 1 1 3
Ma. 2 0 r 09
Mal t b环境下素数筛选算法的分析及比较 a
张琦许勇2,
(. 1西北大学软件学院，陕西西安 7 02;: 17 1
2安徽师范大学数学计算机科学学院， .安徽芜湖 2 10 ) 4. 0 0
摘要：用 Ma a对矩阵科学运算的支持， Maa环境下对埃拉托斯特尼筛法，icl定理衍生的素数筛法、答利 db在 tb l Drh t ie辛
拉姆筛法和基于奇合数分解式的素数筛法进行算法实现和初步优化，并测试其性能，研究发现在计算大范围的素数表
时，法之间的性能差异明显。通过对这些算法的比较和评价，析各个算法的优缺点。研究结果表明 .于不同环境要算分对
求和不同的待解问题需要选取合适的素数筛选算法，因此.文中结论具有一定的指导意义和实际参考价值。
关键词： tb素数；法 Maa; l筛中图分类号： P 0 . T 316文献标识码： A文章编号：6 3 69 (0 90— 0 5 0 17— 2 X 20 )3 0 9— 4
Ana y i nd Co pa io o e e a iv e h d n i e lssa m rs n fS v r lS e e M t o so Pr m Nu b rS a c i t a lb m e e r h ng wih M ta
Z A GOt x2Y n2 H N i q og,
( . o ee 1S f r, otw s i rt, ia 1 17 C i; 1 C lg ( ot e N r et l f wa h Unv sy X’n7 02, ht ei n i
2 C l e f te t s& C mp t ne A h i r l iesy W uu2 10 C ia . ol hmai g e o Ma c o ue S c, n u ma Un ri, h 4 00, h ) r Ae No v t n
Abta tW i tes p oto sr c: t h u p r fm arx cx p tn fM alh.sv r|cmp trag r h￣ fp i u e er hn iV h ti cn uigo ta e e a o u e lo i ns0 r t men mb rsac ig se emeh d t t
o s h M alb aei l e t a d￥ n￣i rv me to h lo ih f lob on .Afe e erhn n e t gt ep ro r n eo h t r mpe n￣ n o i mpo e n ft eag rt msaeas d e a m e trrsa c i a d tsi h efrm e ft e g n
p o rms b iu ie e c mo gt eeag rtmsi dso ee wh n t rg a,o vo sdf rn ea n h s lo i f h s icv rd e het td t s1r e B n lssa d m mp rs n。te a v n s e aai ag . y a ay i n aio h d a –
rg sa dd b c so h s lo ih I ie a e n “ v a k ft eeag rtmsa℃gv n.Th ee rh p ) ta ifrnte vrn n sa d dfee trltd p blmsn e ersa c 玎1髑 h tdfee n i me t n ifrn eae r e ed o o tea p o raese em eh dt e hep i u e rdi r to h p rp it iv to og tt rmen mb s i in.S h eer hr dt hsp p rh ssresg iia c d pa tcl t bu ot rsac e t i a e a on infcn ea rcia e s of n
v le . au s
Ke yⅥ叼 S ralb;p i n t b r iv to I:n ta rme mae;se emeh d
O引言
素数的性质及其分布是数论研究的核心问题之
一
1几种常见的素数筛选算法及其实现
1埃拉托斯特尼筛法 J )。 简称埃氏筛或爱氏筛，是一种由埃及数学家埃拉托斯特尼所提出的一种简单检定素数的算法。他在寻
,
目前人类尚未找出素数的分布规律。但随着计算
技术的快速发展，在一个大数范围内快速筛选出素数
已经成为可能。素数的筛选方法很多，如埃拉托斯特尼筛法、 icl定理衍生的素数筛法、 Dr h t i e辛答拉姆筛法、基于奇合数的分解式的素数筛法等，此类方法在计
算机算法中均有实现，但对这些算法的实现讨论并不多见。文中选择 Ma a环境， db针对目前应用的上述素
找整数 N以内的素数时，
先将 2一N的各数写在纸上： 在 2上面做上标记，然后划去 2的其他倍数；一个既第
未标记又没有被划去的数是 3将它标记，,再划去 3的
其他倍数；既未标记又没有被划去的第一个数是现在 5将它标记，去5,并划的其他倍数……依此类推，一直
到所有小于或等于』的各数都做上标记或划去为止。\『
这时，做上标记的以及未划去的那些数正好就是小于 N的素数。
数筛选算法进行分析及比较。
收稿日期：0 8—0一l 20 6 5基金项目：徽省自然科学基金重点项目(0 5 j0 Z 安 2 0 k 9 D) 0
算法实现：先设定一个 1×N的单位向量(假设墨
作者简介：张
法设汁；许
琦( 9 7一，,徽芜湖人， 18 )男安研究方向为程序和算
勇，授，教博士，士生导师，硕主要从事计算机网络、网
筛选的范围为 N)向量中的零代表非素数，零 (,非一般是 1代表素数， )筛选时将准备筛去的非索数在行向
量中对应值设为 0筛选后剩下的行向量中值为 1,的数
络安全、网络教育方面的研究。
