Hackerrank – Problem description
The problem description – Hackerrank.
Solution
We can use the algorithm where we find out a list of all prime number divisor – prime factorization.
Let find the beginning prime number. The smallest prime number is 2. We divide the given number with actual divisor (actual prime number) until the division is possible. Then we change the prime number divisor with next prime number. We continue this steps until the division result is smaller than 1. Pick the biggest divisor.
There are other prime factor algorithms, e. g. Pollard Rho or Quadratic_sieve
I created solution in:
All solutions are also available on my GitHub profile.
Ruby
|
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; } } |