3

My python 2.7 code which has been coded based on Eratosthenes prime sieve, to find all the primes under a certain limit, gives a memory error when finding primes over billion. In my code, I simply used a list to store true/false values corresponding to each number(true when it is a prime, false otherwise). Below is my code,`

def primeSieve(limit):
   sieve = [True] * ((limit+1)/2)
   for i in range(3, int(limit**0.5)+1, 2):
      if sieve[i/2]:
        sieve[(i*i)/2::i] = [False] * ((limit-i*i-1)/(2*i)+1)
   return [2] + [2*i+1 for i in range(1, (limit+1)/2) if sieve[i]]

print primeSieve(100000000)

How can I modify my code to find primes over billion ? Thank you.

ShadowRanger
  • 143,180
  • 12
  • 188
  • 271
UdhanIsuranga
  • 131
  • 1
  • 8
  • Are you using 32-bit or 64-bit version of Python 2.7? – Matthew Hart Oct 30 '17 at 12:27
  • The sieve of Eratosthenes isn't really suitable for numbers over a billion. The memory requirements are enormous, and in most cases it's far more efficient to use Miller-Rabin instead. – r3mainer Oct 30 '17 at 12:45
  • Also, how much RAM do you have installed, and how much is available on your system prior to running this program? A billion 32-bit integers is 4 GB. – Patrick87 Oct 30 '17 at 12:46
  • @Matthew Hart, I am using 64 bit version – UdhanIsuranga Oct 30 '17 at 13:13
  • @Patrick87, I have installed a 4 GB RAM – UdhanIsuranga Oct 30 '17 at 13:17
  • 1
    Use a [segmented sieve](https://stackoverflow.com/a/10249801/448810) to find larger primes. – user448810 Oct 30 '17 at 14:43
  • 1
    Well 64-Bit python uses 64 bytes for an empty list and then 8 more for each element in it, using simply math a billion elements would need `(8*1000000000 + 64)/1024**3` GB of RAM, or 7.451GB, which you don't have – Nick is tired Nov 04 '17 at 09:52
  • Start by looking at [Making Sieve of Eratosthenes more memory efficient in python?](https://stackoverflow.com/q/62899578/5987). I'm tempted to mark this one as a duplicate. – Mark Ransom Dec 11 '20 at 02:14
  • Does this answer your question? [Making Sieve of Eratosthenes more memory efficient in python?](https://stackoverflow.com/questions/62899578/making-sieve-of-eratosthenes-more-memory-efficient-in-python) – ShadowRanger Dec 11 '20 at 02:28
  • @Nick with virtual memory, running over your installed RAM won't make the program fail - it will just make it really really slow. I don't dispute your memory requirement estimate though. – Mark Ransom Dec 11 '20 at 04:10

0 Answers0