File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/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 Soft Skills this week in the Jobs Discussion 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: 8419
    
  23

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
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: Faster Sum of Prime Numbers