无聊之中，做了一个质数判断，尚待完善

aoe1981 · 发表于 2014-1-20 11:07

hnwxm 发表于 2014-1-20 10:27
用产生素数表的方法即可，当然可以再提速，一般讲没必要。

产生素数表的方法，这个提法好，概括性强，高手！！！

lee1892 · 发表于 2014-1-20 12:43

楼住的几个问题：

1、素性判定
有很多快速的素性判定：
  Fermat Primality Test
  Solovay - Strassen Primality Test
  Miller - Rabin Primality Test
  Baillie - PSW Primality Test
  Elliptic Curve Primality Proving
  AKS Primality Test
最后两种是确定的判定一个数是否为素数，其余的都是高阶的可能性判定，即存在错误的可能。具体实现方式不妨在网上查一下。

2、素因数分解
通用且省事的办法，是根据自己需要，预先生成一定量的素数，如十万内或是百万内的，作为常数编译到程序里或是作为资源文件用的时候动态调用，更大的素数则是在此基础上通过筛选法计算而得。在需要对较大数作素因数分解的时候，完全动态的生成素数表是非常笨拙的方式，那是业余数学爱好者干的。

3、超大数的计算
超大数的计算是通过数组实现的，将一个数组理解为某个基数下的进制，每一个元素对应该进制下的某一位，比如十进制时第一个元素是个位数，第二个是十位数。通常基数选择为2的某次方或是10的某次方，前者适应计算机的内存和计算，后者对人而言更直观。
可以参考一下开放竞赛区里计算根号2那个帖子，基本的加减乘除四则运算在该贴里有正确的实现方法。

香川群子 · 发表于 2014-1-20 14:36

aoe1981 发表于 2014-1-19 23:27
我测试到的一维数组最大上标是9637 0679，运行了24秒，得出素数个数556 4258，稠密度约5.77%。上标为9637 ...

你这个代码算法很明确，就是筛子法。

但是即使在VBA代码中，也还是有改进余地。

我研究了一下，做了test2、test3、test4一共3个阶段的改进，
现在test4可以达到Excel VBA算法的极限了。

我目前测试最大n=25*10^7 也可以计算，而且速度提高不少。

下面代码你去验证一下吧：

Const n As Long = 25 * 10 ^ 7 'k=13,679,317
Sub SpeedCompare()
Dim i&, j&, n&, p&
p = 0
Debug.Print " ": Debug.Print "-Begin-"
For j = 4 To 4
tms = Timer
For i = 1 To 10 ^ p
Run "Test" & j
Next
Debug.Print "Test" & j & ": " & Format(Timer - tms, "0.0000s")
Next
Debug.Print "--End--"
End Sub
Sub test1()
Dim i&, j&, k&, flag() As Boolean, arr&(), tms#
' tms = Timer
ReDim flag(n), arr(n)
For i = 2 To Sqr(n)
If Not flag(i) Then
For j = 2 * i To n Step i
flag(j) = True
Next
End If
Next
For i = 3 To n
If Not flag(i) Then arr(k) = i: k = k + 1
Next
ReDim Preserve arr(k - 1)
' MsgBox Format(Timer - tms, "0.000s ") & k
' If k < 65536 Then [a:a] = "": [a1].Resize(k) = Application.Transpose(arr)
End Sub
Sub test2()
Dim i&, j&, k&, flag() As Boolean, arr&(), tms#
' tms = Timer
ReDim flag(n), arr(n \ 10)
For i = 2 To n Step 2
flag(i) = True
Next
For i = 3 To Sqr(n) Step 2
If Not flag(i) Then
For j = 3 * i To n Step i * 2
flag(j) = True
Next
End If
Next
For i = 3 To n
If Not flag(i) Then arr(k) = i: k = k + 1
Next
ReDim Preserve arr(k - 1)
' MsgBox Format(Timer - tms, "0.000s ") & k
' If k < 65536 Then [b:b] = "": [b1].Resize(k) = Application.Transpose(arr)
End Sub
Sub test3()
Dim i&, j&, k&, flag() As Boolean, arr&(), tms#
' tms = Timer
ReDim flag(n \ 2), arr(n \ 10)
For i = 3 To Sqr(n) Step 2
If Not flag((i + 1) / 2) Then
For j = 3 * i To n Step i * 2
flag((j + 1) / 2) = True
Next
End If
Next
For i = 2 To n \ 2
If Not flag(i) Then arr(k) = i * 2 - 1: k = k + 1
Next
ReDim Preserve arr(k - 1)
' MsgBox Format(Timer - tms, "0.000s ") & k
' If k < 65536 Then [c:c] = "": [c1].Resize(k) = Application.Transpose(arr)
End Sub
Sub test4()
Dim i&, j&, k&, m&, t&, flag() As Boolean, arr&(), tms#
tms = Timer
m = n \ 2
ReDim flag(m)
' If n < 10 ^ 6 Then ReDim arr(m) Else ReDim arr(m \ 5)
For i = 2 To Sqr(n) \ 2
If Not flag(i) Then
t = i * 2 - 1
For j = (i * 3 - 1) To m Step t
' t2 = j * 2 - 1
flag(j) = True
Next
End If
Next
For i = 2 To m - 2
If Not flag(i) Then k = k + 1 'arr(k) = i * 2 - 1: k = k + 1
Next
' ReDim Preserve arr(k - 1)
MsgBox Format(Timer - tms, "0.000s ") & Format(k, "#,##0")
' If k < 65536 Then [d:d] = "": [d1].Resize(k) = Application.Transpose(arr)
End Sub

复制代码

水刀梁 · 发表于 2020-7-19 05:52

aoe1981 发表于 2014-1-19 12:10
整理一下，以下代码可概括为：2＋划2序列，大数据下估计此代码最优！

为了给大数据运算做准备，又做了优 ...

您老人家这样不断在窗体里改，没人愿意每次测试都去修改一次，写成Sub或Fun，更多人会参与进来的。

水刀梁 · 发表于 2020-7-20 15:27

香川群子发表于 2014-1-20 14:36
你这个代码算法很明确，就是筛子法。

但是即使在VBA代码中，也还是有改进余地。

香川群子老师，拜读，研究中

水刀梁 · 发表于 2020-7-21 05:00

lee1892 发表于 2014-1-20 12:43
楼住的几个问题：

1、素性判定

老师您好！30位以内超大数的运算可以使用小数化处理吗？

香川群子 · 发表于 2020-9-12 10:53

水刀梁发表于 2020-7-21 05:00
老师您好！30位以内超大数的运算可以使用小数化处理吗？

不可以。小数计算是浮点运算，位数多了误差很大。

因此，只能采用整数运算。

VBA中，可以使用数字的CDec()格式运算，可以计算28位精度的整数。

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

无聊之中，做了一个质数判断，尚待完善

评分