java - 我如何在没有暴力破解的情况下做 Euler 5？

Question

在我当前的 Project Euler problem 5 ，我有一个“有效”的解决方案。它适用于较小的数字(问题中的示例)，但不适用于实际问题，因为我在强行使用它，并且程序没有完成。

问题的解释如下:

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?

¹: Divisible with no remainder

这是我当前的代码:

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 到 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 )找出所有不超过 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