Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- from math import ceil, isqrt
- MAX_PRIME = 94906249
- # MAX_PRIME = 4294967291
- BITMAP_SIZE = ceil((MAX_PRIME - 1) / 24)
- bitmap = bytearray(BITMAP_SIZE)
- MAX_NUMBER = 24 * BITMAP_SIZE + 1
- limit = isqrt(MAX_NUMBER)
- if limit % 6 not in {1, 5}:
- limit -= limit % 6 - 1 if limit % 6 else 1
- i_bound = limit // 3
- j_bound = MAX_NUMBER // 3
- masks = tuple(0b1000_0000 >> i for i in range(8))
- for i in range(i_bound):
- if not (bitmap[i >> 3] & masks[i & 7]):
- prime = 3 * i + 5 - (i & 1)
- j1 = (prime * prime) // 3 - 1
- j2 = j1 + (prime << (1 + (i & 1))) // 3
- step = prime << 1
- for j in range(j1, j_bound, step):
- bitmap[j >> 3] |= masks[j & 7]
- for j in range(j2, j_bound, step):
- bitmap[j >> 3] |= masks[j & 7]
- with open('prime-bitmap.bin', 'wb') as f:
- f.write(bitmap)
Advertisement
Add Comment
Please, Sign In to add comment
