# Faster Sum of Prime Numbers

posted 4 years ago

I am trying to solve "sum of prime numbers upto N" where N<=1000000 for given number of test cases.

It is just a small modification of this code. Sieve of Eratosthenes.

I tried implementing Sieve of Atkins but that is even more slower than the above one for finding sum (Or may be I am doing something wrong).

I can see there are many unnecessary iterations done in this code for which I just skipped the body of loop by writing this statement at the beginning of body

For example : when

i =2 and j=6 => i*j = 12

i =3 and j=4 => i*j = 12 // Redundant

or

i =2 and j=15 => i*j = 30

i =3 and j=10 => i*j = 30 // Redundant

i =5 and j=6 => i*j = 30 // Redundant

But still it is iterating more times than necessary (only the body is not executing). How do I completely remove these redundant iterations or Is there any other way to solve this problem more efficiently ?

This code is exceeding the given time limit. Please help.

It is just a small modification of this code. Sieve of Eratosthenes.

I tried implementing Sieve of Atkins but that is even more slower than the above one for finding sum (Or may be I am doing something wrong).

I can see there are many unnecessary iterations done in this code for which I just skipped the body of loop by writing this statement at the beginning of body

For example : when

i =2 and j=6 => i*j = 12

i =3 and j=4 => i*j = 12 // Redundant

or

i =2 and j=15 => i*j = 30

i =3 and j=10 => i*j = 30 // Redundant

i =5 and j=6 => i*j = 30 // Redundant

But still it is iterating more times than necessary (only the body is not executing). How do I completely remove these redundant iterations or Is there any other way to solve this problem more efficiently ?

This code is exceeding the given time limit. Please help.

Live Curious!!!

posted 4 years ago

Well, your inner (

And as far as efficiency goes, it's usually best to store the results of calculations. For example, you calculate

As for other methods: there are plenty, but many of the fastest ones involve recursion, and I don't know if you've covered that yet.

Another tip for you which may be useful: All prime numbers > 3 have the pattern 6k±1.

HIH

Winston

Sagar Dabas wrote:But still it is iterating more times than necessary (only the body is not executing). How do I completely remove these redundant iterations or Is there any other way to solve this problem more efficiently ?

Well, your inner (

`j`) loop is running many more times than it needs to. (Tip: don't

*increment*

`j`).

And as far as efficiency goes, it's usually best to store the results of calculations. For example, you calculate

`i*j`four times, the last three of those are redundant. Multiplications are also quite a bit slower than addition/subtraction.

As for other methods: there are plenty, but many of the fastest ones involve recursion, and I don't know if you've covered that yet.

Another tip for you which may be useful: All prime numbers > 3 have the pattern 6k±1.

HIH

Winston

"Leadership is nature's way of removing morons from the productive flow" - Dogbert

Articles by Winston can be found here