Big Moose Saloon
 Search | Java FAQ | Recent Topics Register / Login

# Putting prime numbers into an array

Rujal Duale
Greenhorn

Joined: Dec 13, 2005
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 ]
Paul Clapham
Bartender

Joined: Oct 14, 2005
Posts: 17085

4

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

Joined: Dec 13, 2005
Posts: 5
Ok Paul, array over-flow is taken care.
Minh Huy Nguyen
Greenhorn

Joined: Dec 13, 2005
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 ]
Ravisekhar Kovuru
Greenhorn

Joined: Sep 23, 2003
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 ]
Jim Yingst
Wanderer
Sheriff

Joined: Jan 30, 2000
Posts: 18670
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?)

"I'm not back." - Bill Harding, Twister
Ravisekhar Kovuru
Greenhorn

Joined: Sep 23, 2003
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 ]
Junilu Lacar
Bartender

Joined: Feb 26, 2001
Posts: 4242

2

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

Joined: Jan 30, 2000
Posts: 18670
[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

Joined: Dec 13, 2005
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.

subject: Putting prime numbers into an array