Hackerrank – Popis problému
Celý popis zadania sa nacháza – Hackerrank.
Riešenie
Na začiatku som si vytvoril zoznam všetkých prvočísel medzi 2 a 106 (horné ohraničenie úlohy). Využil som jeden z najznámejších algoritmov – Eratostenovo sito.
Potom pre každý test vezmem podmnožinu prvočísel menších ako zadaný vstup a urobím súčet čísel podmnožiny.
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 53 54 55 56 57 58 59 60 61 62 63 |
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class SummationPrimes { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int tests = scanner.nextInt(); List<Long> primes = eratosthenes(1000000); for (int i = 0; i < tests; i++) { int n = scanner.nextInt(); System.out.println(sum(primes, n)); } scanner.close(); } private static long sum(List<Long> primes, int n) { long sum = 0; for (long prime : primes) { if(Long.compare(prime, n) > 0) { return sum; } sum += prime; } return sum; } private static List<Long> 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 ((long) j * i < array.length) { array[j * i] = false; j++; } } } List<Long> primes = new ArrayList<Long>(); for (int i = 2; i < array.length; i++) { if(array[i]) { primes.add((long) i); } } return primes; } } |