|
楼主 |
发表于 2015-1-29 15:59
|
显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用 · 内置多项VBA编程加强工具 ★ 免费下载 ★ ★ 使用手册★
因此有推论:
如果一个数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值越大,差异越大……到后面可以相差几万倍!
这个,就是算法的力量。(到目前为止,是数学知识的力量)
但并非到此为止,还可以继续有算法上的重大改进、提高。
并且不仅仅依靠数学知识,还需要代码熟练、巧安排。
呵呵。
|
评分
-
1
查看全部评分
-
|