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
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.
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 incrementj).
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.
Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here