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; } } |