Project Euler - 005

dorodaloo

Project Euler - 005

题目：

• 2520 is the smallest number that can be divided by each of the numbers from 1 to 10  without any remainder.
• What is the smallest positive number that is evenly divisible by all of the numbers from 1 to 20?
  

• 2520是最小的能被1-10中每个数字整除的正整数。
• 最小的能被1-20中每个数整除的正整数是多少？
  

dorodaloo

1. package main
   
2. 
   
3. import "math"
   
4. 
   
5. func main() {
   
6.         p005(10)    // 2520
   
7.         p005(20)    // 232792560
   
8. }
   
9. 
   
10. func p005(n int) {
    
11.         var rec = make([]int, n+1)
    
12.         for i := range rec { rec[i] = 0 }
    
13.         for i := 2; i <= n; i++ {
    
14.                 j := i
    
15.                 m := 2
    
16.                 var num = make(map[int]int)
    
17.                 max := int(math.Sqrt(float64(j)))
    
18. 
    
19.                 for m <= max {
    
20.                         if j%m != 0 { m++; continue }
    
21.                         num[m]++; j /= m
    
22.                 }
    
23.         
    
24.                 num[j]++
    
25.         
    
26.                 for k := range num {
    
27.                         if rec[k] < num[k] { rec[k] = num[k] }
    
28.                 }
    
29.         }
    
30.    
    
31.         var res = 1
    
32. 
    
33.         for i := 2; i <= n; i++ {
    
34.                 if rec[i] == 0 { continue }
    
35.                 res *= int(math.Pow(float64(i), float64(rec[i])))
    
36.         }
    
37.    
    
38.         println(res)
    
39. }
    
40. 
    
41. // 题目：
    
42. // 2520 is the smallest number
    
43. // that can be divided by each of the numbers from 1 to 10
    
44. // without any remainder.
    
45. // What is the smallest positive number that is evenly divisible by
    
46. // all of the numbers from 1 to 20?
    

复制代码