Two Laptop Bag
The moose likes Java in General and the fly likes Finding a prime number Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Finding a prime number" Watch "Finding a prime number" New topic

Finding a prime number

Ian Cockcroft
Ranch Hand

Joined: Apr 05, 2001
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

- Make it idiot proof and they'll make a better idiot!
karl koch
Ranch Hand

Joined: May 25, 2001
Posts: 388
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.
Ian Cockcroft
Ranch Hand

Joined: Apr 05, 2001
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.
attaching my code so you can see what I did
Greg Charles

Joined: Oct 01, 2001
Posts: 2968

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

Joined: Apr 05, 2001
Posts: 46
Thanks Charles.
Math.sqrt() works better I'm sure.
Just have to work out how join works.
Thanks again.
William Wild

Joined: Dec 10, 2002
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.
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.

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

Joined: Oct 12, 2001
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'):
[ April 25, 2003: Message edited by: Rene Larsen ]

Regards, Rene Larsen
Dropbox Invite
Rene Larsen
Ranch Hand

Joined: Oct 12, 2001
Posts: 1179

I've done some 'optimization' to your code :-)

[ April 25, 2003: Message edited by: Rene Larsen ]
I agree. Here's the link:
subject: Finding a prime number
jQuery in Action, 3rd edition