• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Liutauras Vilda
  • Tim Cooke
  • Jeanne Boyarsky
  • Bear Bibeault
Sheriffs:
  • Knute Snortum
  • paul wheaton
  • Devaka Cooray
Saloon Keepers:
  • Tim Moores
  • Stephan van Hulst
  • Ron McLeod
  • Piet Souris
  • Ganesh Patekar
Bartenders:
  • Tim Holloway
  • Carey Brown
  • salvin francis

Faster Sum of Prime Numbers

 
Ranch Hand
Posts: 47
PHP C++ Java
  • 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.
 
Bartender
Posts: 10777
71
Hibernate Eclipse IDE Ubuntu
  • 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
 
He baked a muffin that stole my car! And this tiny ad:
Enterprise-grade Excel API for Java
https://products.aspose.com/cells/java
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!