Skip to content

Instantly share code, notes, and snippets.

@sergey-shambir
Created April 22, 2018 15:29
Show Gist options
  • Save sergey-shambir/01fbce4d2430767d4928a8c229a2898e to your computer and use it in GitHub Desktop.
Save sergey-shambir/01fbce4d2430767d4928a8c229a2898e to your computer and use it in GitHub Desktop.
Estimate Erastosthenes Sieve size required to find I-th prime number
import math
def sieve_size_bytes(number_bits):
max_index = 2**number_bits
max_prime = max_index * math.log(max_index)
number_bytes = (number_bits) + 7) / 8
sieve_size = long(math.sqrt(max_prime) * number_bytes / 3)
return sieve_size
print("size for 32-bit index: " + str(sieve_size_bytes(32)))
print("size for 64-bit index: " + str(sieve_size_bytes(64)))
# Outputs:
# size for 32-bit index: 411534
# size for 64-bit index: 76283622977
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment