Rujal Duale

Greenhorn

Posts: 5

posted 11 years ago

However you should probably add some code to break out of the loop after you fill in the last entry in the array.

Nothing.what should I do when it ain't prime?

However you should probably add some code to break out of the loop after you fill in the last entry in the array.

Minh Huy Nguyen

Greenhorn

Posts: 1

Ravisekhar Kovuru

Greenhorn

Posts: 25

posted 11 years ago

<hr></blockquote>

You don't need to loop thru until

It is enough to loop thru until

This is based on the mathematical fact that

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

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

[ December 16, 2005: Message edited by: Ravisekhar Kovuru ]

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

Sheriff

Posts: 18671

posted 11 years ago

I added [code] tags to the above posts to improve readability. Please use these in the future.

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

**[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

Posts: 25

posted 11 years ago

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 ]

BTW, you want to use "code" tags to preserve indentation, not "quote"

[ December 16, 2005: Message edited by: Junilu Lacar ]

*Practice only makes habit, only perfect practice makes perfect.
Practice mindfully by doing the right things and doing things right.*— Junilu

[How to Ask Questions] [How to Answer Questions]

Jim Yingst

Wanderer

Sheriff

Sheriff

Posts: 18671

posted 11 years ago

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.

**[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.

"I'm not back." - Bill Harding, *Twister*