Hackerrank - Project Euler+ #012 - Highly divisible triangular number

Hackerrank – Popis problému

Celý popis zadania sa nacháza – Hackerrank.

Riešenie

Prechádzam všetky čísla od 1 po N. Potrebujem urobiť celočíselný rozklad čísla na prvočísla. Vznikne nám takýto stav:

$n = p_1^{e_1} * p_2^{e_2} * \ldots$

. Prvočísla si viem určiť napr. cez Eratosthenovo sito. Určím si exponenty. Urobím product hodnôt všetkých exponentov:

$divisors = \prod_{i=1}^{count~of~e} {e_i + 1}$

.
Ak má nejaké číslo hodnotu

$divisors$

väčšiu ako zadaný počet, vypíšeme ho, lebo to je náš výsledok.

Celočíselný rozklad nám umožnuje získať celkový počet deliteľov. Napr.

$6$

je deliteľné

$2$

$3$

, teda rozklad

$6$

na prvočísla je:

$6 = 2^1 \times 3^1$

Ak si rozložíme číslo

$24$

$24 = 2^3 \times 3^1$

Všetky delitele

$24$

sú kombinácie čísel vzniknutých kombinovaním daného rozsahu exponentu. Napr. pre

$24$

môžme

$2$

kombinovať od

$0$

$3$

$0$

$1$

. Vznikne tieto kombinácie:

1 = 2^0 * 3^0
2 = 2^1 * 3^0
3 = 2^0 * 3^1
4 = 2^2 * 3^0
6 = 2^1 * 3^1
8 = 2^3 * 3^0
12 = 2^2 * 3^1
24 = 2^3 * 3^1

1 = 2^0 * 3^0

2 = 2^1 * 3^0

3 = 2^0 * 3^1

4 = 2^2 * 3^0

6 = 2^1 * 3^1

8 = 2^3 * 3^0

12 = 2^2 * 3^1

24 = 2^3 * 3^1

Pre

$24$

máme

$8$

deliteľov – jeden exponent má hodnotu

$3$

a druhý hodnotu

$1$

. Ale keďže môžme použiť aj

$0$

ako exponent. Teda musíme vynásobiť každý exponent zvýšený o

$1$

$8 = (3 + 1) * (1 + 1)$

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 HighlyDivisibleTriangularNumber
{
	public static void main(String[] args)
	{
		Scanner scanner = new Scanner(System.in);
		List<integer> primes = eratosthenes(10000000);

		int tests = Integer.parseInt(scanner.nextLine());
		for (int i = 0; i < tests; i++)
		{
			int num = 0;
			int div = 0;
			int divisors = Integer.parseInt(scanner.nextLine());
			outer: for (int number = 1; number < Integer.MAX_VALUE; number++)
			{
				int counter = 1;
				num += number;
				int n = num;
				for (int j = 0; j < primes.size() && div < n; j++)
				{
					div = primes.get(j);
					int exp = 0;
					while (n % div == 0)
					{
						exp++;
						n /= div;
					}
					counter *= (exp + 1);
					if (counter > divisors)
					{
						System.out.println(num);
						break outer;
					}
				}
			}
		}
		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;
		}
		List<integer> primes = new ArrayList<integer>();
		for (int i = 2; i < array.length; i++)
		{
			if (array[i])
			{
				int j = i;
				while (i * j >= 0 && i * j < array.length)
				{
					array[i * j] = false;
					j++;
				}
				primes.add(i);
			}
		}
		return primes;
	}
}
</integer></integer></integer></integer>

import java.util.ArrayList;

import java.util.List;

import java.util.Scanner;

public class HighlyDivisibleTriangularNumber

{

public static void main(String[] args)

{

Scanner scanner = new Scanner(System.in);

List<integer> primes = eratosthenes(10000000);

int tests = Integer.parseInt(scanner.nextLine());

for (int i = 0; i < tests; i++)

{

int num = 0;

int div = 0;

int divisors = Integer.parseInt(scanner.nextLine());

outer: for (int number = 1; number < Integer.MAX_VALUE; number++)

{

int counter = 1;

num += number;

int n = num;

for (int j = 0; j < primes.size() && div < n; j++)

{

div = primes.get(j);

int exp = 0;

while (n % div == 0)

{

exp++;

n /= div;

}

counter *= (exp + 1);

if (counter > divisors)

{

System.out.println(num);

break outer;

}

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;

}

List<integer> primes = new ArrayList<integer>();

for (int i = 2; i < array.length; i++)

{

if (array[i])

{

int j = i;

while (i * j >= 0 && i * j < array.length)

{

array[i * j] = false;

j++;

}

primes.add(i);

}

return primes;

}

</integer></integer></integer></integer>

Pavol Pidanič

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

Hackerrank – Project Euler+ #012 – Highly divisible triangular number

Hackerrank – Popis problému

Riešenie

Java

Leave a Reply Cancel reply