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

ljx63426 · 发表于 2015-1-29 15:13

通俗易懂，好好学习，请继续讲下去！！！

江河行地. · 发表于 2015-1-29 15:30

慢慢品味了!

香川群子 · 发表于 2015-1-29 15:39

对于本帖问题，第一个重大的改进来源于数学知识：

在所有2-N的正整数集合中，所有合数（可以分解为至少两个以上素数因素的乘积的数）中，
至少有1个素数因素的值，比N的开方即 Sqr(N)要小或至少相等。

即，如果把2-N中任意1个合数（包括N，如果N也正好是合数的话），
分解为两个数的乘积（此时这两个数不限定为素数）时，
如果故意分成一个取其中最小的素数，另一个为剩余素数的连乘积时，
则最小的那一个素数的值，一定不大于N的开方即Sqr(N)

数学证明如下：
假设 1 < X <=N 且X 为合数可分解为 X=Y1*Y2*……Ym （其中Y都是素数，且Y1<=Y2<=……<=Ym）

则强令 X分解为两个数的乘积时，即 X=Y1*(YY) （其中YY=Y2*……Ym ）

那么反证：如果Y1 > Sqr(N) 则两边乘方就是 Y1*Y1>N
而由于Y1<=Y2<=……<=Ym 所以 YY=Y2*……Ym 必定至少>=Y1

所以，就会有 X=Y1*YY>=Y1*Y1>N ……这就和最初的条件 1 < X <=N 不符合了。

…………
证明完毕。

…………
上述证明虽然逻辑很简单，但对于数学不好的人来说，可能还是有些理解困难。

但是，如果举出几个简单例子说明一下就可以了。

例-1 如果有N=121，则Sqr(N)=11
那么，2-121的整数中，会有哪一个的合数，可以分解为2个数的乘积，而且其中最小的那一个数都比11大呢？

如果有，则这个最小的数至少不小于11，我们就算它=12，
（如果必须是素数则这一个数应该=13，但我们就忍让一些，算它=12好了。）
因为两个数都要比11大，那么这个合数就只会比=12*12=144更大……这显然已经超出了 2-121的数字范围。

…………
顺便继续下去，其实2-121所有合数分解后，最小的素数的最大值就是=11，这个合数就是121，即121=11*11
但是，在2-121的整数范围中，则不可能找到能分解为2个数的乘积，且其中最小的1个素数比11更大的合数了。

举例为：
119=7*17 ……虽然其中1个的素数17>11，但最小的素数仅为=7<11

120=2*60 ……虽然另一个数=60>11，但最小的素数仅为=2<11

117=3*39 ……虽然另一个数=39>11，但最小的素数仅为=3<11

113=1*113 ……这是1个素数，只能被1和自身整除。所以不是我们刚才要求的合数。

…………

以上说明如不懂，则应多看几遍，反复体会。

cpy123581321 · 发表于 2015-1-29 15:49

要学好算法可能还要学好数学啊！

这，是我从小到大的痛！

香川群子 · 发表于 2015-1-29 15:59

因此有推论：

如果一个数N不能被所有<=Sqr(N)的素数整除，则它自己就是一个素数了。

因为，如果它是1个合数，则必然含有一个<=Sqr(N)的素数因数。（证明过程见上帖。）

…………
因此，到这里，求2-N范围中所有素数的算法的重大算法改进就呼之欲出了……

【对于所有2-N的正整数来说，仅需遍历检查 2-Sqr(N)范围的整数是否能整除即可】
而无需像test1那样，遍历计算所有2-N的整数了。

Sub test2()
Dim i&, j&, k&, n&, s&
n = [a1]
ReDim a(1 To n) As Boolean
For i = 2 To n
s = Sqr(i) '计算对于整数 i 来说，可能含有的最小素数的最大值=Sqr(i)
For j = 2 To s '仅需检查2-Sqr(i)范围内的整数
If i Mod j = 0 Then Exit For '能被整除时即可判断为合数，提前中途退出检查
Next
If j <= s Then a(i) = True '判断如果发生了中途退出检查，则为合数
Next
ReDim b&(1 To n)
For i = 1 To n
If a(i) = False Then k = k + 1: b(k) = i '提取检查后的结果
Next
ReDim Preserve b&(1 To k)
' If k < 65536 Then [b:b] = "": [b1].Resize(k) = Application.Transpose(b)
End Sub

复制代码

呵呵，就这么一个改动，速度提高了10倍以上，而且N值越大，差异越大……到后面可以相差几万倍！

这个，就是算法的力量。（到目前为止，是数学知识的力量）

但并非到此为止，还可以继续有算法上的重大改进、提高。
并且不仅仅依靠数学知识，还需要代码熟练、巧安排。

呵呵。

香川群子 · 发表于 2015-1-29 16:25

下面是test3的算法变化：

Sub test3()
Dim i&, j&, k&, n&, s&
n = [a1]
ReDim a(1 To n) As Boolean
For i = 2 To Sqr(n) '检查素数改为 i 在外层循环
'检查2-Sqr(i)范围内的整数
For j = i + 1 To n '被检查对象改为 j 在内层循环
If j Mod i = 0 Then a(j) = True
Next
Next
ReDim b&(1 To n)
For i = 1 To n
If a(i) = False Then k = k + 1: b(k) = i
Next
' [a2] = k
ReDim Preserve b&(1 To k)
' If k < 65536 Then [b:b] = "": [b1].Resize(k) = Application.Transpose(b)
End Sub

复制代码

有意思的是，这样的算法改进似乎失败了……
因为计算耗时反而增加了2-3倍（虽然比之前的直接全循环检查要快3-4倍）

Zamyi · 发表于 2015-1-29 16:39

以为多高明，比近四年前的帖子还差许多！
http://club.excelhome.net/thread-697413-4-1.html 38楼

Zamyi · 发表于 2015-1-29 16:43

哈哈，只能说数学还差。第一点，排除偶数，第二点，只需检查Sqrt(n)的质数就行。

香川群子 · 发表于 2015-1-29 16:45

继续，算法改进test4

Sub test4()
Dim i&, j&, k&, n&, s&
n = [a1]
ReDim a(1 To n) As Boolean
For i = 2 To Sqr(n)
If a(i) = False Then
'增加当前除数 i 是否为素数的判断（如已倍整除标记为=True合数则无需用于检查）
For j = i + 1 To n
If j Mod i = 0 Then a(j) = True
Next
End If
Next
ReDim b&(1 To n)
For i = 1 To n
If a(i) = False Then k = k + 1: b(k) = i
Next
ReDim Preserve b&(1 To k)
' [a2] = k: If k < 65536 Then [b:b] = "": [b1].Resize(k) = Application.Transpose(b)
End Sub

复制代码

这样处理以后，速度大为提高，赶上了代码2的速度。

…………
这么做虽然结果上看用处不大，但其实仔细读一下这些代码的算法是有较大差异的。
尽管使用了相同的数学知识作为算法依据，但实现过程，即循环的安排顺序、处理过程，
则完全是靠VBA的程序算法能力了。

…………为什么要这么做呢？

这些就是自我学习、自我进步的诀窍！

对同一个问题反复思考，考虑各种代码实现的可能性，并因此而对代码更加熟悉，
对于今后的编程会更加得心应手。

…………
就我的经验来说，很多新手VBA的爱好至，其实脑子是很僵硬的，
对于某一个问题来说，往往都是直线思维，在自己的少得可怜的工具库里随便翻一翻，
然后就不管手里面是大刀还是长矛就那么上了……思路非常地不灵活，

一心想着要一次到位得到结果，完全没有能力和兴趣研究各种方法的用法。
而且这样长期下去，即使过了很多年，也写了不少代码，却依然水平不能提高……呵呵。

香川群子 · 发表于 2015-1-29 16:56

算法真正的突破：

这个比test2速度又快了4-5倍……比test1已经快了50-60倍了。

Sub test5()
Dim i&, j&, k&, n&, s&
n = [a1]
ReDim a(1 To n) As Boolean
For i = 2 To Sqr(n)
If Not a(i) Then
For j = i + i To n Step i '这里是改进关键，注意循环步长 i 是变化的。
a(j) = True
Next
End If
Next
ReDim b&(1 To n)
For i = 1 To n
If a(i) = False Then k = k + 1: b(k) = i
Next
ReDim Preserve b&(1 To k)
' [a2] = k: If k < 65536 Then [b:b] = "": [b1].Resize(k) = Application.Transpose(b)
End Sub

复制代码

本次算法的重大改进，在于彻底废除了Mod算法，而改为数组定位后直接标记的做法。

原理在于，数组 a(1 To n) 是完全按顺序排列的，
因此，如果其中某些元素的位置正好能被整数 i 整除，
那么它们一定是 i、i+i、i+i+i、i+i+i+i、i+i+i+i+i…… 即 i 的整数倍实际上就是以 i 开始、步长= i 的等差数列。
或者直接简化为 i、i*2、i*3、i*4、i*5、

因此，无需进行Mod计算，即可按照顺序，用For循环来直接标记所有 i 的整数倍的合数所在位置了。

仅需理解这一句的代码：
For j = i + i To n Step i
i + i 即 i*2 含义是：该素数 i 的本位无需排除，之后的 i+i、或 i*2 位置开始直到终点n，以步长 i 循环即可。

呵呵。

由于省去了大量的Mod计算的时间，所以代码速度大为提高。

		自动登录	找回密码
密码			免费注册

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

点评

评分

点评

点评

点评

点评

评分

点评

评分

最新热点 /1

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

点评

评分

点评

点评

点评

点评

评分

点评

评分

最新热点 /1

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