## Hackerrank – Problem description

The problem description – Hackerrank.

## Solution

The challenge has upper constraint that we could have at most `10 001`

prime numbers from the smallest (`2`

).

I found out that the upper bound is the number `104 743`

. There exist first `10 001`

prime numbers. We calculate list all of them and print the required index of the prime number.

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 |
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class Prime10001st { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int tests = Integer.parseInt(scanner.nextLine()); // naive solution - from analysis 10001st prime is 104 743 // constraint says primes to 10^4th // first I list all primes to 104 743 and then get index List<Integer> primes = eratosthenes(104743); for (int i = 0; i < tests; i++) { int n = Integer.parseInt(scanner.nextLine()); System.out.println(primes.get(n - 1)); } 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 >= 0 && 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; } } |