Project Euler : Problem 5 - Smallest multiple

Problem Statement : Smallest multiple

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$?

Concept and Theory

The question can be translated into find the LCM of all the numbers between $1$ and $20$. This can be further translated to find the highest power of each prime number between $1$ and $20$.

All you have to do is calculate the prime numbers below the given number with their highest power and multiply them. That’s it. Its a fun problem if you know how to find the highest power of a number in a factorial (Find the maximum power of a number below a factorial) and how to find prime numbers below a given number $N$ (Calculate Primes).

Code

/**
 * A function to calculate the Maximum Power Of a Number In Factorial
 *
 * @param num
 *            the factorial number
 * @param a
 *            the number whose highest power needs to be calculated
 *
 * @return the maximum power of number in Factorial
 */
public static long maximumPoweredValueOfNumberInFactorial(long num, long a) {

  long maxPower = 0;
  long currentNumber = a;
  while (num > currentNumber) {
    currentNumber *= a;
    maxPower++;
  }

  return maxPower;
}

/**
 * A function to find out the smallest multiple which can be evenly divided by
 * all the numbers from 1 to num
 *
 * @param num:
 *            maximum limit of the number
 *
 * @return smallest multiple
 */
public static long smallestMultiple(long num) {
  long[] primeArray = new long[] { 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37 };

  long smallestMultiple = 1;

  for (int i = 0; primeArray[i] <= num; i++) {
    long highestPowerNumber = (long) Math.pow(primeArray[i],
        maximumPowerOfNumberInFactorial(num, primeArray[i]));
    smallestMultiple *= highestPowerNumber;
  }

  return smallestMultiple;
}

Test Your Skills

Wanna try a harder version of the above problem ? Check this HackerRank problem.

Solution

The solution will remain same as above method $smallestMultiple$, you just need to call it for each test case.

References and Further Readings

• ProjectEuler