## Hackerrank – Problem description

The problem description – Hackerrank.

## Solution

We need to make a prime factorization of number (problem constraints), because some of the numbers are divisors of the other numbers. We reduce unnecessary multiplications and divisions.

We could use Sieve of Eratosthenes to calculate all prime numbers from `2`

to `N`

.

Let’s calculate how many times is a prime number in given number. It will look like the following equation:

where

denotes how many times is a prime

in a given number.

We can calculate

for every number.

to

are taken from Sieve of Eratosthenes algorithm. Last step is to calculate exponents

. We can calculate as:

and do it for every prime number.

I created solution in:

All solutions are also available on myGitHub profile.

## Java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 |
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class SmallestMultiple { // prime factorization // http://www.mathblog.dk/project-euler-problem-5/ public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int tests = Integer.parseInt(scanner.nextLine()); for (int i = 0; i < tests; i++) { int number = Integer.parseInt(scanner.nextLine()); List<integer> primes = eratosthenes(number); long result = 1; for (int prime : primes) { int exp = (int) (Math.log(number) / Math.log(prime)); result *= (long) Math.pow(prime, exp); } System.out.println(result); } scanner.close(); } private static List<integer> eratosthenes(int number) { boolean[] array = new boolean[number + 1]; for (int i = 0; i < array.length; i++) { array[i] = true; } for (int i = 2; i < array.length; i++) { if(array[i]) { int j = i; while (i * j < array.length) { array[i * j] = false; j++; } } } List<integer> primes = new ArrayList<integer>(); for (int i = 2; i < array.length; i++) { if(array[i]) { primes.add(i); } } return primes; } } </integer></integer></integer></integer> |