我如何在没有暴力的情况下完成Euler 5？

Question

在我当前的项目Euler问题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

您正在寻找的数字是1,2,3,...,20数字的最小公倍数（LCM）。

通过将每个数字拆分为其素因子的乘积（对于小数字来说很容易），找到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, 3, ..., m (m <= n)

然后，对于每个素数a，求出幂pa，使得

<代码>a**pa

但是

<代码>a**（pa 1）

答案将会是

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