Win a copy of Clojure in Action this week in the Clojure forum!
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic

Faster Sum of Prime Numbers

 
Sagar Dabas
Ranch Hand
Posts: 47
C++ Java PHP
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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.
 
Winston Gutkowski
Bartender
Pie
Posts: 9472
50
Eclipse IDE Hibernate Ubuntu
  • 0
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
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
 
  • Post Reply
  • Bookmark Topic Watch Topic
  • New Topic