multithreading to calculate primes java

Question

I am trying to parallelize a prime number counter as an exercise. I have refactored the original code and separated the long loops from others so that I can parallelize them. Now I have the following code and multithreading is looking difficult as I need to keep track of the primes found (in order) and count the number of primes found.

nthPrime(long n) gets the number of primes to search for. returns the nth prime. count is an ArryList

public static long nthPrime(long n) {

    count.add((long) 1);
    if (n < 2) {
        count.add((long) 3);
        return getCount();
    }
    count.add((long) 3);
    if (n == 2) {
        return getCount();
    }

    step = 4;
    candidate = 5;
    checker(n, step, candidate);
    return getCount();
}

private static long checker(long n, int step, long candidate) {

    while (count.size() < n) {
        if (Checker.isPrime(candidate)) {
            // checks the number for possible prime
            count.add(candidate);
        }

        step = 6 - step;
        candidate += step;
    }
    return getCount();
}

Any ideas on using util.concurrent or threading to parallelize this?

Thanks

Translating my [multi-threading Sieve of Eratosthenes](http://stackoverflow.com/a/18885065/549617) from C# to Java, will get a working program up to a reasonable range (up to 10^14 in a few hours). The trick is to not make the multi-threading too fine grained but to do (as there) coarse multi-treading, in this case by page segments per thread. Your problem is that you require the list of primes as well as the count, meaning enumerating the primes, meaning that the time to enumerate them will be much longer than the optimized time of eliminating the composites. — GordonBGood, May 28 '16 at 02:02

Stephen C · Answer 1 · 2013-10-26T03:23:35.560

Two pieces of advice:

Before you start, you need to turn your existing non-parallel code into something that 1) works and 2) is readable. Attempting to pararllelize it in its current form is going to lead to failure.
- I can see bugs (I think)
- I can't see evidence that you understand the basic sieving algorithm ... which is what it appears you are trying to implement here.
Anyone can take an algorithm split it into bits and use multiple Java threads to execute the bits. The difficulty is coming up with a scheme which works, and where your efforts actually give a worthwhile speedup. That requires:
- a good understanding of the problem and the applicable algorithms,
- identifying the part of the problem / algorithm that are amenable to parallelization,
- understanding of the overheads and potential bottlenecks in Java multithreading, and
- understanding of the correctness issues; e.g. where and how to synchronize.
I can't give you a lesson on these things in the space of a StackOverflow Answer. You need a text book.

the full algorithm is in the Checker.isPrime(candidate) method. I have refactored it so that the code will be easier to read. the loop inside the checker method is what I want to parallelize. — Pramuditha Niroshan Ranasinghe, Oct 26 '13 at 03:34
Yes, I was clarifying the lack of algorithm in the code. Thanks — Pramuditha Niroshan Ranasinghe, Oct 26 '13 at 05:04

multithreading to calculate primes java

1 Answers1