aspose file tools*
The moose likes Beginning Java and the fly likes Faster Sum of Prime Numbers Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Beginning Java
Bookmark "Faster Sum of Prime Numbers" Watch "Faster Sum of Prime Numbers" New topic
Author

Faster Sum of Prime Numbers

Sagar Dabas
Ranch Hand

Joined: Nov 15, 2011
Posts: 47

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.


Live Curious!!!
Winston Gutkowski
Bartender

Joined: Mar 17, 2011
Posts: 8008
    
  22

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


Isn't it funny how there's always time and money enough to do it WRONG?
Articles by Winston can be found here
 
It is sorta covered in the JavaRanch Style Guide.
 
subject: Faster Sum of Prime Numbers