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;
}
}
Tuesday, May 1, 2018
Trial Division for integers up to Integer.MAX_VALUE in java
Subscribe to:
Posts (Atom)