SHARE
TWEET

Untitled

a guest Oct 19th, 2019 57 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. import java.util.HashMap;
  2. import java.util.Map;
  3.  
  4. class Scratch {
  5.     public static void main(String[] args) {
  6.         long number = 600851475143L;
  7. //        long number = 13195;
  8.         long result = findLargestPrimeFactor(number);
  9.         System.out.println(result);
  10.     }
  11.  
  12.     private static long findLargestPrimeFactor(long number) {
  13.         long squareRoot = (long)Math.ceil(Math.sqrt(number));
  14.         Map<Long, Boolean> eratosthenesReturn = eratosthenesSieve(squareRoot);
  15.         long max = Integer.MIN_VALUE;
  16.         for (long l : eratosthenesReturn.keySet()) {
  17.             if (l > max && !eratosthenesReturn.get(l) && (number % l == 0))
  18.                 max = l;
  19.         }
  20.         return max;
  21.     }
  22.  
  23.     private static Map<Long, Boolean> eratosthenesSieve(long max) {
  24.         // boolean = is composite. false if prime
  25.         Map<Long, Boolean> sieve = new HashMap<>();
  26. //        sieve.put(2L, false);
  27. //        sieve.put(3L, false);
  28.         for (long i = 2; i <= max; i++) {
  29.             sieve.put(i, false);
  30.         }
  31.         for (long i = 2; i < max; i++) {
  32.             if (!sieve.get(i)) {
  33.                 for (long j = i * 2; j < max; j += i) {
  34.                     sieve.put(j, true);
  35.                 }
  36.             }
  37.         }
  38.         return sieve;
  39.     }
  40. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top