关于互质数

自然数m,n,m∈(1,x),n∈(1,y)，求m,n互质（即m,n 最大公约数为1）的概率

x,y 驱于无穷大时，此概率的极限为6/π^2

Function GETPMN(ByVal X As Long, Y As Long) As Double
Dim a() As Byte, i As Long, temp As Double, p As Long
If X > Y Then
temp = X
X = Y
Y = temp
End If
If X = 1 Then GETPMN = 1: Exit Function
GETPMN = 1 - ((X \ 2) / X) * ((Y \ 2) / Y)
ReDim a(1 To X)
p = 3
Do While p <= X
If p <= Sqr(X) Then
temp = p * p
k = 0
For i = temp To X Step 2 * p 'p的倍数
a(i) = 1 '设为1表示合数
Next
End If
GETPMN = GETPMN * (1 - ((X \ p) / X) * (Y \ p) / Y)
again:
p = p + 2
If p > X Then Exit Do
If a(p) = 1 Then GoTo again
Loop
End Function

Private Sub Command1_Click()
Dim mytime As Double
mytime = Timer
Debug.Print "x=20000000,y=10000000 时， m,n互质的概率为：" & GETPMN(20000000, 10000000); "总计用时 " & Format(Timer - mytime, "0.0000") & " 秒！"

End Sub

返回:

x=20000000,y=10000000 时， m,n互质的概率为：0.607927217465724 总计用时 2.1254 秒！