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

hehex

香川群子 发表于 2015-1-30 21:44
【最后说一句，群子的代码中似乎使用了 Redim Preserve 这从效率讲是不可取的，因为数组的不变性，Redim  ...

再优化，再如何，vba 中redim 就是要开内存的。而redim preserve 最少有3 个操作，首先在heap 里开新数组的内存，然后从原数组逐一复制数据过去。第三释放原数组内存，如果没有第三步，速度会快点，结果更坏，产生了内存泄漏。
而你根据概算公式或者干脆估算一个较大的数组，则仅是数组定位的指针操作，速度和redim 还有redim preserve 完全不可同日而语。就是定位我取这个数组的前多少位有效，怎么是for 循环呢？你生成新数组之后回去该遍历还是要一样for 的啊。

高度保密

关于质数的相关规律：
1、一个数只有1和它本身两个因数，这个数叫作质数。
2、1既不是质数，也不是合数。
3、2，3，5，7外所有2，3，5，7的倍数都不是质数。
4、2是偶数中唯一的质数，其他质数都是奇数。

香川群子

高度保密 发表于 2015-1-30 22:32
59楼很快，但是部分数据无效，还需要改进 。比如32到122之间的的数会出错。

还有，1不是素数

【但是部分数据无效，还需要改进 。比如32到122之间的的数会出错。】

错误原因：
系数参数表输错1个。第3个系数应为0.5，不是0.25……定义数组太小，导致计算后溢出。

……原帖已更正。

840205910

hehex 发表于 2015-1-30 12:15
其实求质数并不是很初级的算法，尤其到test5 已经很高深了，很不适合初学者了。
转发一篇一位大神（某大 ...

山外有山、天外有天

Bodhidharma

香川群子 发表于 2015-1-30 17:18
本帖问题的算法总结：

① 仅需检查

小時候第一次寫質數表時，只使用了篩法
這個討論串的一系列優化方法，當初都是看一個優秀的程式碼之後
自行揣摩出來的…要是當時有這麼好的教學文件，相信能省下很多時間~
很喜歡這種風格的教學文件，相信對初學者應該很有幫助~

学不完用不尽

学算法，膜拜中！

yuwd3

好贴，先占个楼学习

choesehae

向香川群子致敬!

下标越界

香川群子 发表于 2015-1-29 10:49
最基本、最简单的算法测试test1

要搁我这写，首先会是一个test0()

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

复制代码

补充内容 (2015-2-23 22:15):
怎么下面没人跟回复？那么我继续回复提问了：

下标越界

按群子老师的test9对1千2百万范围内的整数筛选出788060个素数。
想象中按照分块显示输出到excel表格中，分块规则如下：
       每100个素数为一块，每块中按10X10排列；每25个“块”横向排成“一排”，每超过25个块就换“下一排”。于是很自然地有了如下代码：

1. Sub test9()
   
2. 
   
3.     Dim t1, t2, r11, c11, tab1
   
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.     Cells(1, 2) = "test9范围" & n & "耗时" & tim2 - tim1 & "秒"
    
27.     ReDim Preserve b&(1 To k)
    
28.     '[a9] = k: If k < 65536 Then [b:b] = "": [b1].Resize(k) = Application.Transpose(b)
    
29.   
    
30.    t1 = Timer
    
31.    
    
32.         ' r1 = Int((k - 1) / 100) + 1
    
33.          r11 = Int((k - 1) / 2500) + 1
    
34.         
    
35.         
    
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 * (1 + (-1) ^ j) / 2, 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.    
    
45.         Next o, j, i
    
46.   
    
47. 
    
48.    t2 = Timer
    
49.    Cells(1, 3) = "输出耗时" & t2 - t1 & "秒"
    
50.    Cells(1, 4) = k & "个素数"
    
51.    
    
52. End Sub
    

复制代码

结果如下：

输出时间太长了，有办法缩短吗？

另外，为了直观上区分各个数据块，采取了给每个块添加不同底色（且相邻块色差很明显）的方式，但如下图所示，显然失败了，相邻区域经常出现相同底色，产生“连成一片”的效果了，第二问来了：如何设置，使得每块底色不同于四周且对比色差明显。楼下有人继续接吧。

缩放到最小后的整体