Parallel prime factorization using an array of primes up to target

Question

I’ve seen this question already being asked on Stack but I couldn’t find any concrete answer or at least the answer I understand. So here is my question:

How could I parallelize the factorization of a big number?

I’ve seen answers like this: “ … He just needs to spawn a new thread for each factor found, then have some sort of synchronized object to collect all the factors”

But I don’t quite understand how this could be done. Could someone please explain it using an example?

Answer 1

If you have a list of primes. You can do it like this (for real large numbers it can take a while). Use a map to hold a frequency count of prime factors and the number of times they occur.

• continue dividing target by current prime until it doesn't divide
• then use BigInteger to check the value to see if it is a prime (this greatly speeds up the process if the remaining value is huge and a prime).
• continue until all factors have been found or you run out of primes.

long candidate = 498977279919318060L;

Map<Long, Integer> factors = new TreeMap<>();
for (long p : primes) {
    while (candidate % p == 0) {
        factors.compute(p, (k,v) -> v == null ? 1 : v+1);
        candidate/=p;
    }
    if (BigInteger.valueOf(candidate).isProbablePrime(99)) {
        factors.put(candidate,1);
        candidate = 1;
        break;
    }
}
if (candidate != 1) {
    System.out.println("factorization incomplete - stopped at " + candidate);
}

factors.entrySet().forEach(System.out::println);

prints

2=2
3=5
5=1
7=1
19=3
29=1
73=2
101=1
137=1

You can verify the result by first, raising each factor to its frequency and then computing the product of those results using reduce.

long val = factors.entrySet().stream()
        .mapToLong(e -> (long) Math
                .pow(e.getKey().doubleValue(), e.getValue()))
        .reduce(1L, (a, b) -> a * b);

System.out.println(val);

prints

498977279919318060