Hackerrank – Popis problému
Celý popis zadania sa nacháza – Hackerrank.
Riešenie
Máme zadané ohraničenie, že maximálne môžme mať 10 001 nasledujúcich prvočísel od najmenšieho (2).
Analýzou som zistil, že horné ohraničenie prirodzených čísel je 104 743. Tu sa nachádza 10 001 prvočísel. Nájdeme si ich zoznam a ako výsledok vypíšeme ich poradie, aké je zadané na vstupe.
Vytvoril som riešenie v týchto programovacích jazykoch:
Všetky riešenia sú dostupné aj na mojom 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; } } |