Prime Numbers Generating Threads in Java printing twice

Question

I am trying to print prime numbers between one point to another, lets say from 1 to 1000 in one thread and 1000 to 2000 in another thread but when I print each thread using foreach loop it gives me an unordered Arraylist which is printed twice.

I am trying to print 1, 2, 3, 5, 7... using two concurrent threads. Please help me out so that I can better understand threading.

public class PrimeNumberGenerator implements Runnable{

    protected long from, to;
    static ArrayList<Long> primeList = new ArrayList<Long>();

    public  PrimeNumberGenerator(long from,long to)
    {
        this.from = from;
        this.to = to;
    }

    public long count = 0;

    public void run() {
        for(long n=from; n<=to; n++){
            boolean isPrime = true;
            for(long i = 2; i<n; i++) {
                if(n % i==0) {
                    isPrime = false;
                    break;
                }
            }
            if(isPrime) {
                count++;
                primeList.add(n);
            }
        }
    }

    public ArrayList<Long> getPrimes() {
        return primeList;
    }

    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        PrimeNumberGenerator gen1 = new PrimeNumberGenerator(1L,1000L);
        PrimeNumberGenerator gen2 = new PrimeNumberGenerator(1001L,2000L);
        Thread t1 = new Thread(gen1);
        Thread t2 = new Thread(gen2);
        t1.start();

        t2.start();
        t1.join();
        t2.join();
        gen1.getPrimes().forEach(primeList -> System.out.println(primeList));
        gen2.getPrimes().forEach(primeList -> System.out.println(primeList));
    }
}

Since the ArrayList is static, both threads are adding to it. When you call the System.out.println, you are printing the same thread twice. If order matters, I recommend using a TreeSet, which will be ordered. — lordoku, Apr 10 '18 at 17:18
Wouldnt using each object print each thread and then the second one ? — Jainam Shah, Apr 10 '18 at 17:18
@JainamShah Since the list is static both threads use the same instance of it. — lordoku, Apr 10 '18 at 17:19
Furthermore, they access the same instance in a not thread safe way. You were lucky, to not see an exception or data corruption. — Henry, Apr 10 '18 at 17:21
@Iorduku I turned the arrayList into protected and it worked. — Jainam Shah, Apr 10 '18 at 17:21

Neuron · Accepted Answer · 2018-04-10T17:55:42.007

The problem is that you have two threads filling the same ArrayList at the same time, because your ArrayList is static (meaning there will only be one instand shared throughout the whole application)

The first thread may add three numbers, then the second thread adds three numbers and then the first again, resulting in an ArrayList that contains

[1, 2, 3, 1009, 1013, 1019, 5, 7, 11]

Then in the end you (correctly) wait for the Threads to finish and print the same (incorrectly ordered) ArrayList twice!

Just make your ArrayList non static and it will work, that way both PrimeNumberGenerator will have their own ArrayList!

Related: https://stackoverflow.com/questions/797964/what-is-the-exact-meaning-of-static-fields-in-java — Gabriel, Apr 10 '18 at 17:26

lordoku · Answer 2 · 2018-04-10T17:48:31.107

I recommend using a TreeSet to keep the primes ordered. The TreeSet will need to be properly synchronized for multiple thread access.

public class PrimeNumberGenerator implements Runnable {

    protected long from, to;
    static Set<Long> primeList = new TreeSet<Long>();

    public PrimeNumberGenerator(long from, long to)
    {
        this.from = from;
        this.to = to;
    }


    public long count=0;

    public void run() {
        for(long n=from;n<=to;n++) {
            boolean isPrime = true;
            for(long i = 2; i<n; i++) {
                if(n % i==0) {
                    isPrime = false;
                    break;
                }
            }
            if(isPrime) {
                count++;
                synchronized(primeList) {
                   primList.add(n);
                }
            }
        }
    }

    public static ArrayList<Long> getPrimes(){
        //Make a copy so we don't need to synchronize outside of this class
        return new ArrayList<>(primeList);
    }

    public static void main(String[] args) throws Exception {
        // TODO Auto-generated method stub
        PrimeNumberGenerator gen1 = new PrimeNumberGenerator(1L,1000L);
        PrimeNumberGenerator gen2 = new PrimeNumberGenerator(1001L,2000L);
        Thread t1 = new Thread(gen1);
        Thread t2 = new Thread(gen2);
        t1.start();

        t2.start();
        t1.join();
        t2.join();
        PrimeNumberGenerator.getPrimes().forEach(primeList -> System.out.println(primeList));

    }
}

If you make it non static you don't need to use a `TreeSet`. — Neuron, Apr 10 '18 at 17:26
If you make it thread safe, it would actually be nicer to have them share one `TreeSet` (although not static) That answer would get a +1 from me ;) — Neuron, Apr 10 '18 at 17:31
Often you run into problems when having two threads operating on the same object. If you are using concurrency you should seriously read a good tutorial first! Concurrency is a lot more complicated than you might think — Neuron, Apr 10 '18 at 17:32
@LonelyNeuron I've updated my answer so that it addresses the thread safety option. — lordoku, Apr 10 '18 at 17:35

Prime Numbers Generating Threads in Java printing twice

2 Answers2