# Finding a prime number

Ian Cockcroft

Ranch Hand

Posts: 46

posted 13 years ago

Hi all, I have a project for varsity where I have to find all the prime numbers in an array of 1000 int's. The question is actually about threads, start 10 threads each checking 100 ints each for 'primeness'. I have the threads running and thats working fine, my problem is, how do i check for prime now?

The question says I must do this:

Hint:To check a number p for primality, use a loop-structure running

from 2 (not 1!) to p/2. Divide p by the loop index; if the remainder is 0,

then you have found a factor of p, and hence p is not prime.

I get:

Can anyone help with a loop to work out if a number is prime or not.

I have included all my code, maybe there is a better way to do it.

Thamks alot

Ian

The question says I must do this:

Hint:To check a number p for primality, use a loop-structure running

from 2 (not 1!) to p/2. Divide p by the loop index; if the remainder is 0,

then you have found a factor of p, and hence p is not prime.

I get:

Can anyone help with a loop to work out if a number is prime or not.

I have included all my code, maybe there is a better way to do it.

Thamks alot

Ian

- Make it idiot proof and they'll make a better idiot!

karl koch

Ranch Hand

Posts: 388

posted 13 years ago

hi ian

i would start with a single threaded version of your problem.

- write a method that takes a int as an argument and returns true/false according to its "primeness". this method is the implementation of the algorithm you describe.

- then "feed" this method with the numbers in your range and according to the return value print it, put it in a file or play a sound.

- then you can split the work to several threads.

your method could look like:

then you could use it like:

if you still have troubles coding the algo, then post again.

k

i would start with a single threaded version of your problem.

- write a method that takes a int as an argument and returns true/false according to its "primeness". this method is the implementation of the algorithm you describe.

- then "feed" this method with the numbers in your range and according to the return value print it, put it in a file or play a sound.

- then you can split the work to several threads.

your method could look like:

then you could use it like:

if you still have troubles coding the algo, then post again.

k

Ian Cockcroft

Ranch Hand

Posts: 46

posted 13 years ago

OK, got it working, thanks for your help, works like a char.

But a new question arrises.

countPrime is a static int that gets updated after each iteration within each thread, when and how do I display the result. If I put it in main, it print before any threads are even run.

thanks.

attaching my code so you can see what I did

But a new question arrises.

countPrime is a static int that gets updated after each iteration within each thread, when and how do I display the result. If I put it in main, it print before any threads are even run.

thanks.

attaching my code so you can see what I did

- Make it idiot proof and they'll make a better idiot!

posted 13 years ago

It sounds like you need a way to find out if the threads have finished. You might take a look at the join method in the Thread class. I think there's also a ThreadGroup version.

The way you increment the primeCount variable is probably perfectly safe, because ++ tends to be an atomic operation. That is, it always completes as a unit and cannot be interrupted part way through. However, I bet the point of the assignment is to use the "synchronized" keyword to allow safe concurrent access to a shared resource.

And as long as I'm here, running the loops to p/2 is overkill. Going to sqrt(p) is sufficient.

The way you increment the primeCount variable is probably perfectly safe, because ++ tends to be an atomic operation. That is, it always completes as a unit and cannot be interrupted part way through. However, I bet the point of the assignment is to use the "synchronized" keyword to allow safe concurrent access to a shared resource.

And as long as I'm here, running the loops to p/2 is overkill. Going to sqrt(p) is sufficient.

Ian Cockcroft

Ranch Hand

Posts: 46

William Wild

Greenhorn

Posts: 23

posted 13 years ago

You could try a static holding class with a synchronised update method called by each thread when it finds a prime number to store the primes.

Use the thread group class in your main() to monitor all threads using the activeCount() method, which should return 0 when all the threads are dead.

As soon as they are all dead you can sort and display all the primes held in your static class.

You may also want to look at a recursion through the number you have to check that will 'ripple' through the numbers to check if it is a prime. You start by dividing the number in half to get a start max, and then sub-thread off the halfs of this checking the middle value each time. It would be complicated to program but would speed things up a bit. You could use the ThreadGroup again for this, and just call the ThreadGroup.stop() method when a prime is found.

Cheers

Bill.

Use the thread group class in your main() to monitor all threads using the activeCount() method, which should return 0 when all the threads are dead.

As soon as they are all dead you can sort and display all the primes held in your static class.

You may also want to look at a recursion through the number you have to check that will 'ripple' through the numbers to check if it is a prime. You start by dividing the number in half to get a start max, and then sub-thread off the halfs of this checking the middle value each time. It would be complicated to program but would speed things up a bit. You could use the ThreadGroup again for this, and just call the ThreadGroup.stop() method when a prime is found.

Cheers

Bill.

--<p>Bill<p>"Make it idiot proof,<br /> and someone will make a better idiot" -- ANON