跟我学算法 【初级篇】：求某个整数范围内所有素数

香川群子

下标越界 发表于 2015-2-18 17:26
要搁我这写，首先会是一个test0()

补充内容 (2015-2-23 22:15):

不好意思，你的代码有bug，输出结果不正确……

应改为：
Sub test0-2() '对【下标越界】 79楼 2015-2-18 代码的修正   
    Dim i&, j&, k&, n&, a&()
    n = [a1]
  For n = 2 To 123 '加入n循环测试

    ReDim a&(1 To n)
    k = 1
    For i = 2 To n + 1
        a(k) = i
        For j = 2 To i - 1
            If i Mod j = 0 Then k = k - 1: Exit For
        Next j
        k = k + 1
    Next i
    If a(k - 1) > n Then k = k - 1 ': a(k - 1) = "" '此处改参数k即可，无需改a(k - 1)值   
    If k < 65536 Then [b:b] = "": [b1].Resize(k - 1) = Application.Transpose(a)
    '输出有效行数=k-1，而不是=k  
  Next n  'n循环测试
End Sub

香川群子

下标越界 发表于 2015-2-18 17:26
要搁我这写，首先会是一个test0()

补充内容 (2015-2-23 22:15):

对【下标越界】79楼代码的进一步修改（只是个人习惯，但运算效率变化不大因为本身就是最差的算法了）：

1. Sub test0-3()
   
2.     Dim i&, j&, k&, n&, a&()
   
3.     n = [a1]
   
4.    
   
5.     ReDim a&(n)
   
6.     For i = 2 To n
   
7.         a(k) = i
   
8.         For j = 2 To i - 1
   
9.             If i Mod j = 0 Then k = k - 1: Exit For
   
10.         Next
    
11.         k = k + 1
    
12.     Next
    
13.     If k < 65536 Then [b:b] = "": [b1].Resize(k) = Application.Transpose(a)
    
14. End Sub

复制代码

香川群子

下标越界 发表于 2015-2-23 22:22
按群子老师的test9对1千2百万范围内的整数筛选出788060个素数。
想象中按照分块显示输出到excel表格中，分 ...

单元格添加底色是个费时费力的工作。没有意义。

下标越界

香川群子 发表于 2015-2-23 23:28
单元格添加底色是个费时费力的工作。没有意义。

嗯，是没意义，存在于想象中即可。
群子老师，我知道我歪楼了。

香川群子

下标越界 发表于 2015-2-23 22:22
按群子老师的test9对1千2百万范围内的整数筛选出788060个素数。
想象中按照分块显示输出到excel表格中，分 ...

我的素数矩阵输出代码：

单元格不加底色时，运算和输出都很快的。

1. Sub PrimeTable() '生成输出筛子法素数矩阵表
   
2.     Dim i&, j&, k&, l&, m&, n&, r&, s&, t&, c&
   
3.    
   
4.     s = 120 '输入<=250的整数 作为输出正方形矩阵的边长s、如n=10、n=100、n=250
   
5.     t = Int(250 / s) '计算得到2003工作表中横向展开的最多矩阵个数t
   
6.     n = Val(InputBox("请输入纵向矩阵数、即" & s * s * t & "的倍数n=[1-100]", "生成输出筛子法素数矩阵表", Int(Rnd * 100 + 1)))
   
7.     If n < 1 Or n > 100 Then Exit Sub Else n = n * s * s * t '纵向矩阵数n换算得到求素数最大范围n
   
8.    
   
9.     '以下为计算范围内素数
   
10.     m = (n - 1) \ 2: ReDim a(1 To m) As Boolean
    
11.     For i = 1 To Sqr(n) \ 2
    
12.         If a(i) = False Then
    
13.             For j = i * 3 + 1 To m Step i * 2 + 1
    
14.                 a(j) = True
    
15.             Next
    
16.         End If
    
17.     Next
    
18.    
    
19.     '以下为按边长s的矩阵、把各个素数转换为输出数组b要求的行列坐标
    
20.     ReDim b(1 To n / s / t, 1 To s * t)
    
21.     b(1, 1) = 1: b(1, 2) = 2
    
22.     For i = 1 To m
    
23.         If a(i) = False Then
    
24.             k = i * 2
    
25.             l = k - Int(k / s / s) * s * s
    
26.             r = Int(l / s) + 1 + Int(k / s / s / t) * s
    
27.             c = l Mod s + 1 + (Int(k / s / s) Mod t) * s
    
28.             b(r, c) = k + 1
    
29.         End If
    
30.     Next
    
31.    
    
32.     Cells = "" '清空
    
33.     [b2].Resize(n / s / t, s * t) = b '输出
    
34. End Sub

复制代码

香川群子

但是，如果要一下子输出4800行*250列=120万个单元格，这个只有看硬件配置了。差一点的电脑只有死机。

大海很宽

好东西，楼楼多写点东西吧。

下标越界

香川群子 发表于 2015-2-24 00:42
我的素数矩阵输出代码：

单元格不加底色时，运算和输出都很快的。

仔细阅读了一下群子老师的输出代码，仅用一层循环实现了方阵输出：
For i = 1 To m
        If a(i) = False Then
            k = i * 2
            l = k - Int(k / s / s) * s * s                      ‘计算当前素数在当前构造方阵里的序号（范围1到 s X s）
            r = Int(l / s) + 1 + Int(k / s / s / t) * s      ‘计算行号： Int(l / s) + 1计算当前素数在当前构造方阵里所在行数，Int(k / s / s / t) * s 计算当前构造方阵“上方”紧邻的行数。两者加起来就是当前素数在“区域”中的所在行数。
            c = l Mod s + 1 + (Int(k / s / s) Mod t) * s     ‘计算列号： l Mod s + 1计算当前素数在当前构造方阵里所在的列数，(Int(k / s / s) Mod t) * s 计算当前构造方阵前面“Int(k / s / s)”个完整方阵中经过横向展开后余下“边角料”方阵的个数，由于每个方阵为s X s，所以当前构造方阵前面“(Int(k / s / s) Mod t) ”个“边角料”方阵占用了“(Int(k / s / s) Mod t) * s ”列。于是当前素数在“区域”中的列数是两者之和。
            b(r, c) = k + 1      '将素数存入二维数组  
        End If
    Next

下标越界

      用群子的代码测试输出1千2百万范围内的素数，发现速度很快，仅几秒钟，而本人在80楼测试的输出时间达到近80秒。两相比较一下就看出：群子使用了二维数组整体输出到excel表格中，大大提升了输出速度，节约了大量时间。于是我把80楼的代码稍稍改动了一下：

1. Sub test9()
   
2. 
   
3.     Dim t1, t2, r11, c11, tab1, arr()
   
4. 
   
5.     Dim i&, j&, k&, m&, n&, tim1, tim2
   
6.     n = [a1]
   
7.    
   
8.       tim1 = Timer
   
9.     m = (n - 1) \ 2: ReDim a(1 To m) As Boolean
   
10.     For i = 1 To Sqr(n) \ 2
    
11.         If a(i) = False Then
    
12.             For j = i * 3 + 1 To m Step i * 2 + 1
    
13.                 a(j) = True
    
14.             Next
    
15.         End If
    
16.     Next
    
17.    
    
18.     nSize = Array(1, 1, 0.5, 0.17, 0.125, 0.1, 0.08, 0.067, 0.058, 0.055)
    
19.     k = n * nSize(Log(n) / Log(10))
    
20.     ReDim b&(1 To k): b(1) = 1: b(2) = 2: k = 2
    
21.     For i = 1 To m
    
22.         If a(i) = False Then k = k + 1: b(k) = i * 2 + 1
    
23.     Next
    
24.    
    
25.     tim2 = Timer
    
26. 
    
27.     ReDim Preserve b&(1 To k)
    
28.     '[a9] = k: If k < 65536 Then [b:b] = "": [b1].Resize(k) = Application.Transpose(b)
    
29.   Cells.Clear
    
30.    t1 = Timer
    
31.    
    
32.         ' r1 = Int((k - 1) / 100) + 1
    
33.          r11 = Int((k - 1) / 2500) + 1
    
34.         
    
35.    ReDim arr(1 To r11 * 10, 1 To 250)
    
36.         
    
37. On Error Resume Next
    
38.         For i = 1 To r11
    
39.           For j = 1 To 25
    
40.             Set tab1 = Cells(1 + (i - 1) * 10 + 1, 1 + (j - 1) * 10 + 1)
    
41.             Range(tab1, tab1.Offset(9, 9)).Interior.Color = RGB(255 * Round(Rnd), 255 * Round(Rnd), 255 * Round(Rnd)) '(1 + (-1) ^ (j + 1)) / 2)
    
42.             For o = 1 To 100
    
43.              ' Cells(Int((o - 1) / 10) + 1 + (i - 1) * 10 + 1, (o - 1) Mod 10 + 1 + (j - 1) * 10 + 1) = b((i - 1) * 2500 + (j - 1) * 100 + o)
    
44.                arr(Int((o - 1) / 10) + 1 + (i - 1) * 10, (o - 1) Mod 10 + 1 + (j - 1) * 10) = b((i - 1) * 2500 + (j - 1) * 100 + o)
    
45.         Next o, j, i
    
46.         
    
47.      
    
48.     [b2].Resize(r11 * 10, 250) = arr '输出
    
49.    ' MsgBox arr(2, 2)
    
50.    t2 = Timer
    
51.    
    
52.    Cells(1, 2) = "test9范围" & n & "耗时" & tim2 - tim1 & "秒"
    
53.    Cells(1, 3) = "输出耗时" & t2 - t1 & "秒"
    
54.    Cells(1, 4) = k & "个素数"
    
55.    
    
56. End Sub

复制代码

运行结果如图：

输出耗时缩短

        综合以上，算不算是一个”空间换时间“的例子呢？

C:\Users\wen\Pictures\输出耗时缩短

zhouzhongchi

从1楼至20楼受益匪浅。本人数学不及格，余下楼层头大，跑马观花。