用VBA解欧拉计划题目（5）

grf1973

第5题：最小倍数

2520是最小的能够被1到10整除的数。

最小的能够被1到20整除的正数

1. Sub problem5()  '找出能被1-20整除的最小自然数（结果是232792560）
   
2.     n = 20
   
3.     arr = Array(2, 3, 5, 7, 11, 13, 17, 19)
   
4.     Set d = CreateObject("scripting.dictionary")   '记录每个数分解各质因数的个数
   
5.     For Each x In arr '先把所有质数过一遍，次数计为1
   
6.         d(x) = 1
   
7.     Next
   
8.    
   
9.     For m = 4 To n
   
10.         If Not d.exists(m) Then   '如果是合数
    
11.             nn = m
    
12.             For Each x In arr   '分解质因数，得出各质因数的最大次数
    
13.                 p = 0
    
14.                 Do While nn \ x = nn / x
    
15.                    p = p + 1
    
16.                    nn = nn / x
    
17.                 Loop
    
18.                 If p > d(x) Then d(x) = p   '把质因数的最大次数作为当前次数
    
19.             Next
    
20.         End If
    
21.     Next
    
22.    
    
23.     res = 1
    
24.     For Each x In arr
    
25.         res = res * x ^ d(x)
    
26.     Next
    
27.     Debug.Print res
    
28. End Sub

复制代码

是多少？

香川群子

应该就是最小公倍数的计算吧。

香川群子

直接按最小公倍数计算，速度比你的方法快20倍。

1. Sub test1()
   
2.     n = 20
   
3.     s = 1
   
4.     For i = 2 To n
   
5.         s = LCM(s, i)
   
6.     Next
   
7. '    Debug.Print s
   
8. End Sub
   
9. Function GCD(t1, t2) '最大公约数 G.C.D=Greatest Common Divisor
   
10.     If t1 Mod t2 Then GCD = GCD(t2, t1 Mod t2) Else GCD = t2
    
11. End Function
    
12. Function LCM(t1, t2) '最小公倍数 L.C.M=Least Common Multiple
    
13.     LCM = t1 * t2 / GCD(t1, t2)
    
14. End Function

复制代码

grf1973

香川群子 发表于 2017-11-1 16:32
直接按最小公倍数计算，速度比你的方法快20倍。

对啊。我怎么没想到呢？
收用GCD，以后会用到。

香川群子

这个是经典的【辗转相除法】，非常地高效。
你的速度慢，估计是使用了字典。字典比数组或数学计算要慢很多。

grf1973

香川群子 发表于 2017-11-1 16:48
这个是经典的【辗转相除法】，非常地高效。
你的速度慢，估计是使用了字典。字典比数组或数学计算要慢很多 ...

是的。后续做到很多题，用字典慢得要命。
但有时在特别大的数据量中只取部分数据，定义大数组太浪费，有时还会溢出，还得用字典。

香川群子

grf1973 发表于 2017-11-1 16:42
对啊。我怎么没想到呢？
收用GCD，以后会用到。

就本题来说，还可以简化：

1. Sub test2()
   
2.     n = 20
   
3.     s = n
   
4.     For i = n - 1 To 10 Step -1 '<10都没必要再计算
   
5.         s = s * i / GCD(s, i) '最小公倍数 L.C.M=Least Common Multiple
   
6.     Next
   
7.     Debug.Print s
   
8. End Sub
   
9. Function GCD(t1, t2) '最大公约数 G.C.D=Greatest Common Divisor
   
10.     If t1 Mod t2 Then GCD = GCD(t2, t1 Mod t2) Else GCD = t2
    
11. End Function

复制代码

grf1973

有道理。更上一层楼了。

大灰狼1976

逐个找出最小公倍数，速度还行。

1. Sub aaa()
   
2. Dim i&, j&, m, m1, n&, k&, l&
   
3. t = Timer
   
4. n = 20
   
5. m = n / 2 + 1
   
6. For i = m + 1 To n
   
7.   m1 = i: l = 1: k = 2
   
8.   Do
   
9.     If m / k = Int(m / k) And m1 / k = Int(m1 / k) Then
   
10.       l = l * k
    
11.       m = m / k
    
12.       m1 = m1 / k
    
13.     Else
    
14.       k = k + 1
    
15.     End If
    
16.   Loop Until k > i
    
17.   l = l * m * m1
    
18.   m = l
    
19. Next i
    
20. MsgBox m & Chr(10) & Timer - t
    
21. End Sub

复制代码

grf1973

结果正确。