Hackerrank – Popis problému
Celý popis zadania sa nacháza – Hackerrank.
Riešenie
Použijeme algoritmus, kde vytvoríme zoznam všetkých prvočíselných deliteľov, resp. urobíme rozklad na prvočísla – faktorizácia.
Určíme si počiatočné prvočíslo. Najmenšie prvočíslo je 2. Zadané číslo delíme zvoleným deliteľom (prvočíslom) dovtedy, pokiaľ to je možné. Potom pripočítame 1 k deliteľovi. Postup opakujem, až kým zadané číslo, po postupnom delení, je menšie ako 1. Vyberieme najväčší deliteľ..
Algoritmus môžeme zrýchliť, ak tesne po inkrementovaní skontrolujeme, či je druhá mocnina deliteľa viac ako aktuálne číslo po vykonaní delenia. Vtedy už nebudeme vedieť vydeliť iným deliteľom ako so sebou samým. Pretože, ak by sme ešte dokázali vydeliť deliteľom, podiel by bol celé číslo, ktoré sa už nachádza v zozname. Mali by sme ho už v prvej časti algoritmu. Pridáme do zoznamu len samého seba.
Existujé aj iné algoritmy, napr. Pollard Rho alebo Kvadratické sito
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 |
import java.util.ArrayList; import java.util.List; import java.util.Scanner; public class LargestPrimeFactors { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int tests = Integer.parseInt(scanner.nextLine()); for (int i = 0; i < tests; i++) { long number = Long.parseLong(scanner.nextLine()); System.out.println(largestPrimeFactor(number)); } scanner.close(); } // http://en.wikipedia.org/wiki/Pollard's_rho_algorithm // http://stackoverflow.com/questions/23287/largest-prime-factor-of-a-number private static long largestPrimeFactor(long number) { List<Long> factors = new ArrayList<Long>(); long d = 2; while (number > 1) { while (number % d == 0) { factors.add(d); number /= d; } d++; if(d * d > number) { if(number > 1) { factors.add(number); } break; } } return max(factors); } private static long max(List<Long> list) { long max = Long.MIN_VALUE; for (Long l : list) { if(l > max) { max = l; } } return max; } } |