Win a copy of Functional Reactive Programming this week in the Other Languages forum!

# Finding a prime number

Ian Cockcroft
Ranch Hand
Posts: 46
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

karl koch
Ranch Hand
Posts: 388
hi ian

- 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.

then you could use it like:

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

Ian Cockcroft
Ranch Hand
Posts: 46
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

Greg Charles
Sheriff
Posts: 2993
12
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.

Ian Cockcroft
Ranch Hand
Posts: 46
Thanks Charles.
Math.sqrt() works better I'm sure.
Just have to work out how join works.
Thanks again.
Ian

William Wild
Greenhorn
Posts: 23
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.
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.

Rene Larsen
Ranch Hand
Posts: 1179
You also need to look at your 'isPrime(..)' method - e.g. it return 4 as a prime number ;-(
try change:
to (and use 'Math.sqrt(value)' instead of 'value/2'):
Rene
[ April 25, 2003: Message edited by: Rene Larsen ]

Rene Larsen
Ranch Hand
Posts: 1179
I've done some 'optimization' to your code :-)

Rene
[ April 25, 2003: Message edited by: Rene Larsen ]