• Post Reply Bookmark Topic Watch Topic
  • New Topic

Putting prime numbers into an array  RSS feed

 
Rujal Duale
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi there,
Is there a better way (simplier way) of writing this method?

thanks a lot
[ December 16, 2005: Message edited by: Jim Yingst ]
 
Paul Clapham
Sheriff
Posts: 22823
43
Eclipse IDE Firefox Browser MySQL Database
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
what should I do when it ain't prime?
Nothing.

However you should probably add some code to break out of the loop after you fill in the last entry in the array.
 
Rujal Duale
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok Paul, array over-flow is taken care.
 
Minh Huy Nguyen
Greenhorn
Posts: 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
think about the BigO, this way is kind of slow with a big number.
A simpler way is:

[ December 16, 2005: Message edited by: Jim Yingst ]
 
Ravisekhar Kovuru
Greenhorn
Posts: 25
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
<hr></blockquote>
You don't need to loop thru until j < i .
It is enough to loop thru until j < (int) Math.sqrt(i) .
This is based on the mathematical fact that 'if a number is not divisible (with 0 reminder) by any number between 2 and its square root, then it won't be divisible by any number beyond its square root either'

This change will cause a very drastic cut down in execution time.
For example to check if 971 is a prime or not, with j < i the loop will be executed 969 times, where as with j < (int) Math.sqrt(i) the loop will only be executed 29 times.

[ December 16, 2005: Message edited by: Jim Yingst ]
[ December 16, 2005: Message edited by: Ravisekhar Kovuru ]
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I added [code] tags to the above posts to improve readability. Please use these in the future.

[Ravisekhar]: It is enough to loop thru until j < (int) Math.sqrt(i) .

Good idea, but slightly off. If i is 9 for example, Math.sqrt(9) is 3. But the loop will only test j = 2, not j = 3, because of the requirement that j < 3. This needs slight modification. I'd also point out that the sqrt() method need only be called once for each i, before the j loop begins. It's needlessly slow to evaluate sqrt() many times inside the j loop since it's the same for each i.

Another thing to think about - do you really need to test devision by all the numbers from 2 to sqrt(i)? For example, do you need to divide by 4? If the number were divisible by 4, it also would have been divisible by 2, which was tested earlier. Similarly 6 could be skipped, and 8, 9, 10, 12... In fact you could skip every non-prime number here. Is there some way to do that? (Hint: in the original problem, you're building a list of prime numbers. Can we use that?)
 
Ravisekhar Kovuru
Greenhorn
Posts: 25
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yes Jim, you are right,
thanks for pointing out..
So I think this modification would be ok:


And I am not sure about how to skip every non-prime number.
Can some one help in this regard.
[ December 16, 2005: Message edited by: Ravisekhar Kovuru ]
 
Junilu Lacar
Sheriff
Posts: 11477
180
Android Debian Eclipse IDE IntelliJ IDE Java Linux Mac Spring Ubuntu
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Look around the web for "Sieve of Erastosthenes" -- that is what the algorithm is called.

BTW, you want to use "code" tags to preserve indentation, not "quote"
[ December 16, 2005: Message edited by: Junilu Lacar ]
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[Ravisekhar]: And I am not sure about how to skip every non-prime number.

Well, skipping every non-prime number would be the same as using every prime number (from 2 to sqrt(i)). The original poster had a variable named "array" that was basically a list of prime numbers. By looping through that array, you loop through a list of prime numbers. If that's still confusing, I recommend just working on the earlier algorithm and making sure it's working correctly.
 
Rujal Duale
Greenhorn
Posts: 5
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Thanks to all for your help. The programme is working fine and much faster after incorporating Math.sqrt(i). Appreciate it.
[ December 18, 2005: Message edited by: Rujal Duale ]
 
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!