Hackerrank - Project Euler+ #005 - Smallest multiple

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:

$n = p_1^{m_1}p_2^{m_2}p_3^{m_3} \ldots p_n^{m_n}$

where

$m_n$

denotes how many times is a prime

$p_n$

in a given number.

We can calculate

$m_n$

for every number.

$p_1$

$p_n$

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

$m_1 \ldots m_n$

. We can calculate as:

$m_i = \lceil \frac{\log{n}}{\log{p_i}} \rceil$

and do it for every prime number.

I created solution in:

Java

All solutions are also available on myGitHub profile.

Java

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>

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>

Pavol Pidanič

I can count to 1023 with 10 fingers

Hackerrank – Project Euler+ #005 – Smallest multiple

Hackerrank – Problem description

Solution

Java

Leave a Reply Cancel reply