Tuesday, May 1, 2018

Trial Division for integers up to Integer.MAX_VALUE in java

import java.util.Arrays;  
 import java.util.HashSet;  
 import java.util.Set;  
 import java.util.concurrent.ThreadLocalRandom;  
 public class TrialDivision {  
   public static void main(String[] args) {  
     int number = ThreadLocalRandom.current().nextInt(1, Integer.MAX_VALUE);  
     Set<Integer> factors = factorize(number);  
     System.out.printf("\n\nThere are %d factors for number %d and are : \n",  
         factors.size(), number);  
     factors.stream().sorted().forEach(System.out::println);  
   }  
   private static int eliminateFactor(int number, int divisor) {  
     while (number % divisor == 0) {  
       number = number / divisor;  
     }  
     return number;  
   }  
   private static boolean storeFactor(int number, int divisor, Set<Integer> factors) {  
     if (number % divisor == 0) {  
       factors.add(divisor);  
       return true;  
     }  
     return false;  
   }  
   private static Set<Integer> factorize(int number) {  
     Set<Integer> factors = new HashSet<>();  
     factors.addAll(Arrays.asList(1, number));  
     storeFactor(number, 2, factors);  
     number = eliminateFactor(number, 2);  
     int divisor = 3;  
     int sqrt = (int) Math.sqrt(number);  
     while (divisor <= sqrt) {  
       boolean isFactor = storeFactor(number, divisor, factors);  
       number = eliminateFactor(number, divisor);  
       if (isFactor) {  
         System.out.printf("divisor : %d, number : %d, sqrt : %d \n", divisor, number, sqrt);  
         sqrt = (int) Math.sqrt(number);  
       }  
       divisor += 2;  
     }  
     factors.add(number);  
     return factors;  
   }  
 }