如何在沒有暴力強迫的情況下做Euler 5？

Question

在我目前的Project Euler problem 5中，我有一個「工作」解決方案。它適用於較小的數字（問題中的示例），但不適用於實際問題，因爲我蠻力強制它，程序沒有完成。

這裏的問題的說明：

2520是能夠由每個號碼而沒有任何剩餘被劃分爲1〜10的最小數目。

什麼是最小的正數是可以整除所有數字從1到20？

：整除沒有餘

這裏是我當前的代碼：

package Euler; 

public class Euler5 { 

    public static void main(String[] args) { 
    int desiredNumber = 20; 
    boolean exitLoop = false; 
    long counter = 1; 

    while(exitLoop == false) { 
     long loopCounter = 0; 
     for(int i=1;i<=desiredNumber;i++) { 
      if(counter%i==0) { 
       loopCounter++; 
      } 
     } 
     if(loopCounter == desiredNumber) { 
      exitLoop = true; 
      System.out.println(counter); 
     } 
     counter++; 
     } 
    } 
} 

Answer 1

你正在尋找的數字是Least common multiple (LCM)數字1,2,3， ...，20。

通過將每個數字拆分爲它的主要因子的乘法（對於小數字很容易），找到LCM相當容易。

Answer 2

你沒有電腦來回答這個問題。看：如果一個數可以由每個從1數的被劃分到20這意味着它應該是素數的乘積在對應的功率：

2**4 (from 16) 
    3**2 (from 9) 
    5 
    7 
    11 
    13 
    17 
    19 

所以該解決方案是

16 * 9 * 5 * 7 * 11 * 13 * 17 * 19 == 232792560 

因爲答案是相當大我懷疑蠻力是不是合理的方法這裏。

在一般情況下（對於某些n >= 2）全部找出來素數未exeeding的N：

2, 3, ..., m (m <= n) 

然後，對於每一個素數a找出功率pa

a**pa <= n

但

a**(pa + 1) > n

答案是

2**p2 * 3**p3 * ... * m**pm

可能的Java實現：

public static BigInteger evenlyDivisible(int n) { 
    if (n <= 0) 
     throw new IllegalArgumentException("n must be positive"); 
    else if (n <= 2) 
     return BigInteger.valueOf(n); 

    ArrayList<Integer> primes = new ArrayList<Integer>(); 

    primes.add(2); 

    for (int i = 3; i <= n; i += 2) { 
     boolean isPrime = true; 

     for (int p : primes) { 
     if (i % p == 0) { 
      isPrime = false; 

      break; 
     } 
     else if (p * p > i) 
      break; 
     } 

     if (isPrime) 
     primes.add(i); 
    } 

    BigInteger result = BigInteger.ONE; 

    for(int p : primes) { 
     // Simplest implemenation, check for round up errors however 
     int power = (int)(Math.log(n)/Math.log(p)); 

     result = result.multiply(BigInteger.valueOf(p).pow(power)); 
    } 

    return result; 
    } 

...

System.out.println(evenlyDivisible(20)); // 232792560