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

香川群子

本帖适合VBA的初级、中级水平爱好者。

很多业余爱好者，都是从录制宏开始的。
一开始，录制简单宏就可以让Excel做一些繁琐的重复操作，节省了人力，提高了效率。
然而往往录制宏并不是那么聪明，于是产生了各种自己修改代码参数（单元格地址、操作行数、列数等。）的要求。

这以后越走越远，逐步深入到VBA代码中去，
开始学习使用For……Next循环，
然后是Do……Loop不定循环，
…………
然后开始引入【VBA中数组】的概念，大大提高了读写的效率。

其实，学会使用数组，把工作表区域读入二维数组，以及自定义一维数组、多维数组……
这已经是一个了不起的进步了，宏代码的速度也会大大提高。

…………
但是，仅仅到这里，还远远不够……
往往对于复杂要求的计算，或者大数据的反复循环运算，一般爱好者的代码，
比起高手编写的代码，运行速度效率要差（慢）几倍甚至几十倍、几百倍。

虽然新手自己的代码能够达到目的，而且一般使用上的速度差异也不会带来太大的影响……
（比如你的代码运行5-10秒，高手的代码0.02秒就完成，虽然速度差很多，但实际耗时影响并不大）

但是，作为一个有上进心的VBA爱好者，在满足工作目标的基础上，自己努力进一步提高代码效率，
也应该是大家都梦想得到的好事。

…………
然而，有时候十个人写代码就会有十种版本，原因在于大家大都是业余爱好而已，
不是按照正规编程教材教出来的，在学习进步过程中，很多都是靠自己学习和感悟，
所以有差异在所难免。

…………
本帖仅仅希望得到如下目的：
① 介绍一些算法效率改进的小知识，积少成多，逐步改善自己的能力。
② 陪伴大家对VBA算法进行一些基础研究，在研究过程中产生乐趣。

另外，我想强调的是：
各人有各人的风格，尤其是，实际工作生活中，适合自己的才是最好的。
所以，我并不想把自己的想法、做法强加给你，
只是希望通过代码的思路介绍，尽量给大家一些学习参考。

…………
呵呵，言归正传，说一下本帖的问题：
【问题】
已知1个正整数n，问1-n范围内有多少个素数？并列出范围内全部素数。

…………
【问题的数学背景】
任何一个正整数N，按照因素分解结果，可以分成二大类：
① 素数或质数： 除了1和自身以外，不能被其它任何整数X整除。（即 Mod(N,X)<>0）
    例如： 1、2、3、5、7、11、13、17、19、23

② 合数或非质数：可以被其它除了1以外的、小于自身的整数Y整除。即，Mod(N,Y)=0 且Y范围为：(1,n)
    也可以更加明确的表达为：N=Y1*Y2*……Yk   
    举例： 6=2*3、9=3*3、12345=3*5*823、1111111=239*4649


…………
就是这么简单、就是这么任性！

huangyongli

好贴，先占个楼学习

663973866

好话题，关注了。

香川群子

本帖问题，其实是一个经典的数学问题。

用VBA解决问题，那么就需要：
① 解题：
   明确题目的数据来源、规则要求，输出结果的要求。

② 算法构思：
   根据上述信息，思考基本算法。
    即：如何让电脑机器通过代码编程来解决问题。

代码程序的基本要求：
一、Data Input 数据输入：

二、Data PreProcess 数据预处理：
      数据加工以便代码可以进一步运行。
     （需要根据题目规则要求，在普世基本逻辑上扩展计算出更多有用的条件）

三、Calculator Process 编制数据处理过程：
      需要根据目的要求，规化数据的计算处理过程，并在计算过程中逐步得到计算结果。

四、Abstract Process 提取结果的处理过程：
      计算结果需要重新整理，达到规定的要求

五、Result Output 输出结果：
     提取的结果，还需要输出到工作表，或输出为txt文件等……

以上，就是解决问题的步骤。

香川群子

算法构思以后，还需要：

③ Run / Debug  反复运行调试、直到产生预期结果。

④ Error detection / Optimize / Efficiency promote 错误测试/优化/效率提升

⑤ Code fix / Comment 代码固化、注释

…………
这样就算完成了呢。

香川群子

呵呵，还刚开了个头，已经被人占楼了……


…………
上面写代码的基本要求已经介绍完毕，
可以进入正题了。

① 解题：
   明确题目的数据来源、规则要求，输出结果的要求。

1-N的N个正整数中，既有素数、也有合数。
如何区分呢？

…………呵呵，即使数学家也没有好办法……
曾经有大数学家，希望通过素数推算公式，得到确定的素数……
结果应该是失败了。任和一个通式，都无法保证x递增的推算结果，保证是素数。

所以，最后数学家和我们大家一样，只能通过最基本的方法来检查任意一个整数X是否为素数：
① For i = 2 To X - 1 '遍历（1 和 X自身不算）

②    If X Mod i = 0 Then  检查X是否能被第i个整数 来整除

【数学上整除的意味】：
表示 X可以分解为 X = i * j 所以才能有 X / i = j 或 X Mod i = 0) 其中 X, i, j 都是正整数。

③   结果： 如果 For i = 2 To X - 1 '遍历完成以后，没有1个整数可以满足 X Mod i = 0 的要求，
     则验证结束，可以确定 X 为素数。（即 X不能分解为 i * j ，其中 i 和 j 都是>1 且 <X的正整数）

【为啥大于X的整数不用验证？】
答： 如果假设 X = i * j 且 i > X ,则有 j = X / i <1 （因为i > X 即 X < i…… X*1/i < i*1/i ……X/i<1）
       也就是说，j必然为小于1的小数而不是正整数。（正整数的最小值=1，没有比1更小的正整数了。）

所以，只需检查  For i = 2 To X - 1

…………
到这里，第1个测试代码可以呼之欲出了：

核心算法部分：

For i = 2 To X - 1
   If X Mod i = 0 Then Exit For
Next
If i = X Then 素数 Else 合数

…………
呵呵。

cpy123581321

香川老师  你开课吗？   在哪儿啊？

香川群子

最基本、最简单的算法测试test1

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

复制代码

香川群子

代码解释：
Sub test1()
    Dim i&, j&, k&, n&
   
    n = [a1]  '获取数据 即需要计算的整数N 是代码运行前事先写在单元格A1中的1个正整数。

    ReDim a(1 To n) As Boolean
    '定义数组a、用来记录循环检查结果是否为合数
    '【Tips】由于仅需记录True/False 两种状态，所以使用布尔类型Boolean数据格式是最好的。

    '【Tips】建立VBA内存数组时，内存一维数组运算效率比二维数组效率高。
    所以，如果仅需内部使用，应该定义为一维数组。

    '【Tips】建立VBA内存一维数组的额外好处：
    ① 方便在VBE窗口调试时观察计算效果。（如为多维数组则还需要一个一个点击+号展开才能看数据。）
    ② 方便直接使用很多工作表函数进行计算，如Match、Index、Count等。
    ③ 方便进行内部排序、或位置交换……数组定位时一维总是比二维计算方便。
    ④ 方便进行Redim Preserve 操作改变数组大小而不影响已有数据。
    ⑤ 数据量不太大时，可以直接整行输出到工作表内的单元格，而无需使用Transpose转置。
    ⑥ 方便进行各种Filter、Join等操作（注意必须是Variant或String类型数据）


    '以下为上帖中算法的实现。增加了对2-n之间每一个数的遍历循环检查

    For i = 2 To n '检查2-n之间的每一个正整数

        '本代码算法处理的核心部分。
        For j = 2 To i - 1 '对当前这个正整数 i 进行素数检查
            If i Mod j = 0 Then Exit For '如中途能被 j 整除 则可判断为合数而无需检查后面的数了
        Next
        If j < i Then a(i) = True '如 j < i 则为中途退出，所以是合数，在数组a中记录为=True
        ' 【如始终未被整除，则可判断是素数（数学原理见上帖），在数组a中的状态未改变、仍为False
       '【Tips】Boolean类型数组所有元素起始状态都为False，这个性质要好好注意、好好利用

    Next
   
   '到此为止，运算完毕，所以下面是提取结果了。
    ReDim b&(1 To n) '定义长整型Long类型数组b，用于记录符合条件的素数集合。
    For i = 1 To n
        If a(i) = False Then k = k + 1: b(k) = i
        '【Tips】关于数组位置序列号k的递增方法，如果是下标LBound(a)=1开始的数组，则k=k+1需要先出现。
        '           而如果是 LBound(a)=0开始的一维数组，则需先写入数据 b(k) = i（默认k初始值=0）然后进行k=k+1处理。……我个人特别喜欢0开始的数组……好处以后再说，但不应强求大家跟我一样。呵呵
    Next
   
    ReDim Preserve b&(1 To k)
    '数组结果可以ReDim Preserve 处理缩小（因为实际的素数集合个数显然小于全部正整数N的范围）

    If k < 65536 Then [b:b] = "": [b1].Resize(k) = Application.Transpose(b)
    '当数据个数不大于2003工作表行数时，可以输出结果。首先清空B列（[b:b] = ""）
    '【Tips】然后转置输出（前面已经说过，一维数组只能整行输出，如需整列输出则必须转置）
End Sub

suyunlong123

香川群子 发表于 2015-1-29 11:14
代码解释：
Sub test1()
    Dim i&, j&, k&, n&

菜鸟必须收藏 好好研究