programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Devaka Cooray
• Liutauras Vilda
• Jeanne Boyarsky
• Bear Bibeault
Sheriffs:
• Paul Clapham
• Knute Snortum
• Rob Spoor
Saloon Keepers:
• Tim Moores
• Ron McLeod
• Piet Souris
• Stephan van Hulst
• Carey Brown
Bartenders:
• Tim Holloway
• Frits Walraven
• Ganesh Patekar

# Putting prime numbers into an array

Greenhorn
Posts: 5
Hi there,
Is there a better way (simplier way) of writing this method?

thanks a lot
[ December 16, 2005: Message edited by: Jim Yingst ]

Sheriff
Posts: 24594
55

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
Ok Paul, array over-flow is taken care.

Greenhorn
Posts: 1
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 ]

Greenhorn
Posts: 25
<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 ]

Wanderer
Posts: 18671
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
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 ]

Sheriff
Posts: 13563
223
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
Posts: 18671
[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
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 ]

 Consider Paul's rocket mass heater.