Hackerrank - Project Euler+ #005 - Smallest multiple

Hackerrank – Popis problému

Celý popis zadania sa nacháza – Hackerrank.

Riešenie

Je potrebné urobiť faktorizáciu čísla (hranice) na prvočísla, lebo niektoré čísla sú zároveň deliteľmi ostatných čísel. Takto sa zbavíme zbytočného násobenia a skúšania deliť všetky čísla, sú sú deliteľné od 1 po n.

Všetky prvočísla od 2 po N si vieme vypočítať napr. pomocou Eratostenovho sita.

Vypočítame, koľkokrát je dané prvočíslo v zadanom čísle. Dopracujeme sa k niečomu, ako nasledovná rovnica:

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

kde

$m_n$

je početnosť krát prvočísla

$p_n$

v zadanom čísle.

Takto vieme rozložiť každé prirodzené číslo.

$p_1$

až

$p_n$

získame z Eratostenovho sita, zostáva nám už len určiť exponenty

$m_1 \ldots m_n$

. Exponenty vypočítame rovnicou:

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

a urobíme pre každé prvočíslo.

Vytvoril som riešenie v týchto programovacích jazykoch:

Java

Všetky riešenia sú dostupné aj na mojom GitHub 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č

Dokážem na 10 prstoch napočítať do 1023

Hackerrank – Project Euler+ #005 – Smallest multiple

Hackerrank – Popis problému

Riešenie

Java

Leave a Reply Cancel reply