Win a copy of Functional Reactive Programming this week in the Other Languages forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Finding a prime number

 
Ian Cockcroft
Ranch Hand
Posts: 46
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
Ian Cockcroft
Ranch Hand
Posts: 46
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Firefox Browser IntelliJ IDE Java Mac Ruby
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Rene Larsen
Ranch Hand
Posts: 1179
Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
Eclipse IDE Mac OS X
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I've done some 'optimization' to your code :-)

Rene
[ April 25, 2003: Message edited by: Rene Larsen ]
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic