[原创]几分钟生成一千万以内素数表的程序

天山草

[这个贴子最后由天山草在 2006/09/12 07:03pm 第 2 次编辑]

[watermark]'; 文件名:  筛法求质数
'; 求 10 000 000 以内的素数
Private Sub form_Click()
Open "s.txt" For Output As 1       ’生成的素数表文件名
n = 10000000                       ’搜寻一千万以内的素数
Dim a(5000000)                    '; 不允许定义成 a(n/2)         
n2 = n / 2: n4 = Int(Sqr(n))
For i = 2 To n2: a(i) = 2 * i - 1: Next ';被筛选的数是大于等于 3 的奇数
For k = 2 To n4    ';先用质数 a(2)=3 筛，再用后续质数筛
If a(k) = 0 Then GoTo 10  ';若 a(k)=0表示已被筛掉，不是素数，不能做为筛子
For i = 3 * k - 1 To n2 Step a(k): a(i) = 0: Next   ’用某素数筛一遍
10:   Next k
a(1) = 2: m = 0
For i = 1 To n2
If a(i) = 0 Then GoTo 20
m = m + 1: a(m) = a(i)    ';整理 a 数组，把第 m 个素数存在 a(m) 中
20:   Next   
Print "m="; m             ';显示不超过 n 的素数的个数
For i = 1 To m   ';以下按指定格式将 m 个素数显示出来，并存入 s.txt 文件中
aa$ = Str$(a(i)) ';将第 i 个素数转换为字符串
L = Len(Str$(n)) ’测量一下 n 的长度
kk$ = Space$(L - Len(aa$)) + aa$ + ",":    ';结果的显示格式
Print kk$; " ";                            ’显示结果
Print #1, kk$; " ";                        ’并将结果写入文件
t = t + 1
If t = 10 Then t = 0: Print:   ';每显示 10 个素数之后，换行显示
If t = 0 Then Print #1, "  "   ';在文件中每输入 10 个素数之后，换行输入
Next
Close #1                     ’关闭文件语句不要省
     
End Sub
  
上面是本人最近用 VB 语言编写的采用“厄拉多塞”筛法编制一千万以内素数表的计算机程序。在我这台陈旧的机器上运行 6 分钟，可得到 10,000,000 以内的素数表，占用大约 7 M 磁盘空间。如果是一百万以内，40 秒钟可算完。耗时主要用在数据存盘。如果您的计算机是近年买的，速度较快，那么计算所需的时间会少得多。
求出的素数每显示 10 个数就换行，上、下排数字的个位对齐，相邻两数字之间用逗号隔开。写入文件的素数表排版格式同上。
一千万以内的素数共有 664579 个。
许多年以前，在没有电子计算机的时代，就有人编制了一千万以内的素数表。那是一本很厚的书。之后又有了五千万甚至更大的素数表。我想，先辈们为编制这些表肯定花费了大量的时间和精力。我们应该向他们致敬。今天我们有了电子计算机，就有了研究数论的有力武器，例如上面的程序稍加改动，就能研究孪生素数的倒数之和是否收敛；除了 3、5、7这样的“三胞胎”孪生素数外，还有没有其它的“三胞胎”素数。
另外，上面的这个程序还有哪些地方可以改进，也请网友们点评指正。
本来要上传一个“一千万以内的素数表”，怎奈文件太大，超过 500k 十倍，不能上传，只好请网友们使用上述程序自行计算吧。如果您没有 VB 软件，可以很容易改写成其它语言的程序。


[/watermark]

wangyangkee

下面引用由ygq的马甲在 2010/05/11 05:29am 发表的内容：
明显地不懂数学的，硬要凑“热闹”，，，，，

【鉴定】和【评估】结论是：“无知者无畏”式的“蠢货”


ygq的马甲 明显地不懂为人的，硬要凑“热闹”，投了人胎，，，