2

How do I find the sum of all primes up to N, that can be any natural number up to 10^11? Normally I would seive them over an array of boolean, but an array of this length would far pass my heap limit. Is there any quick way that does not require so much memory?

Thanks!

user2705335
  • 357
  • 1
  • 3
  • 8
  • Why do you want to do that ? – skjcyber Nov 09 '13 at 08:02
  • A round of applause to an imaginative lecturer – Ed Heal Nov 09 '13 at 08:05
  • I am asking this particularly now for a riddle I solve. But how to generate primes above heap limit interested me for a very long time regardless, it seems like a very basic problem, so I find it weird that I don't have any clue of it's solution. – user2705335 Nov 09 '13 at 08:07
  • It is a mathematics question. All numbers have factors. Perhaps google that first to understand the problem before putting fingers to code – Ed Heal Nov 09 '13 at 08:08
  • I see what you say Ed. Luckily I'm already very well aware of the problem, so I don't need to do that. (Solving Project Euler for a few months now helps :)) – user2705335 Nov 09 '13 at 08:26
  • 4
    You will need to use a segmented Sieve of Eratosthenes: http://stackoverflow.com/questions/10249378/segmented-sieve-of-eratosthenes. – user448810 Nov 09 '13 at 13:20
  • 1
    With wheel factorization 3.3GB (10^11/30 bytes) would be enough, which today is not that much. But a segmented sieve is better. Try making the segments small enough to fit in cache. – starblue Nov 10 '13 at 08:14

1 Answers1

0

1) If you have a file with all the primes in the given range in form of numbers, you can just load them line by line parsing from text to integer and adding to a sum variable.

2) If you have a boolean array in the file, you can as well load them byte by byte.

If you must calculate yourself, you might want to create the file with primes first and then do 1) or 2)

exebook
  • 32,014
  • 33
  • 141
  • 226