## Hackerrank – Problem description

The problem description – Hackerrank.

## Solution

I check all numbers from `1`

to `N`

. I need to do a prime factorization of each number. In the end there is a following state:

. To calculate the prime numbers I use for example Sieve of Eratosthenes. I calculate the exponents and product of calculated exponent values:

.

If there exists a number with

value greater than given amount, it is the result.

Prime factorization is used for calculating all divisors. For example

is divisible by

and

, so factorized

is:

.

Let’s take for example the number

:

All divisors of

are combinations of numbers when changing range of calculated exponent.There is

prime number to be combined from

to

exponent and

from

to

. These are the combinations:

1 2 3 4 5 6 7 8 |
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 |

There are

divisors for

– one exponent is

and second

. We can use

as an exponent, too. That’s why we have to multiply incremented exponent value.

I created solution in:

All solutions are also available on my GitHub 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 59 60 61 62 63 64 65 66 67 68 |
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> |