Bitwise Sieve Prime Numbers: Complete Bit Operations Guide

Introduction and Core Concepts

Bitwise sieve prime numbers is a memory-optimized variant of the classic Sieve of Eratosthenes that replaces the traditional boolean or integer array with a compact bit array. Instead of using one byte or even one integer per number to mark primality, it packs 32 or 64 numbers into a single machine word, using individual bits to represent whether a number is prime or composite. This technique is a cornerstone of bit manipulation and demonstrates how low-level operations can dramatically improve the scalability of a fundamental algorithm.

At its core, the sieve still follows the same mathematical principle discovered by Eratosthenes: iteratively mark multiples of each prime starting from 2. What changes is the underlying data structure. In a standard sieve, an array is_prime[0..n] might consume n+1 bytes (or more in Python lists). In a bitwise sieve, an array of integers bits[] is used where the k-th bit of the word-th integer corresponds to the number word * 32 + k. This reduces memory consumption by a factor of 32 when using 32-bit words, or 64 when using 64-bit words, enabling the generation of primes up to billions on commodity hardware.

Why does this matter? Prime generation is not just an academic exercise. It underpins cryptography, hashing, random number generation, and performance-critical systems where memory bandwidth and cache locality determine throughput. When n reaches 10^8 or 10^9, a standard boolean sieve can require hundreds of megabytes and thrash the CPU cache, while a bitwise sieve fits comfortably in L3 cache and reduces memory traffic. For competitive programming, embedded systems, and high-performance computing, mastering bitwise sieve prime numbers is essential for writing algorithms that are both time and space efficient.

Core Terminology

To understand the bitwise sieve, you must be familiar with four bit operations: bit set, bit clear, bit test, and bit shift. Setting a bit marks a number as composite, clearing is rarely needed but useful for initialization, testing checks primality, and shifting isolates the correct word and offset. The two key formulas are word_index = i >> 5 (equivalent to i // 32) and bit_offset = i & 31 (equivalent to i % 32) for 32-bit packing. For 64-bit packing, these become i >> 6 and i & 63.

Another critical optimization often combined with the bitwise approach is storing only odd numbers. Since 2 is the only even prime, all even numbers greater than 2 can be ignored entirely, halving memory again. In this odd-only bitwise sieve, bit i represents the number 2*i + 1 or 2*i + 3 depending on indexing, effectively doubling the range for the same memory footprint. This combination is what most production-grade bitwise sieves use in practice.

How It Works

The bitwise sieve operates in three logical phases: initialization, marking, and collection. During initialization, an array of integers is allocated with size (n // 32) + 1 and all bits are set to 0, indicating all numbers are initially presumed prime. Bits for 0 and 1 are explicitly marked as composite (set to 1) since they are not prime by definition. This bit array is the sole state of the algorithm, replacing the larger boolean array.

The marking phase is where the Eratosthenes logic executes using bit operations. Starting from p = 2, the algorithm checks if p is still marked as prime by testing its bit. If it is prime, it marks all multiples of p starting from p*p as composite. Instead of assigning is_prime[multiple] = False, it performs bits[word] |= (1 << offset) to set the bit to 1. The loop only needs to run up to sqrt(n), because any composite number larger than sqrt(n) will have already been marked by a smaller prime factor. This is identical to the classic sieve, but the marking operation is now a read-modify-write on a bit field.

The efficiency comes from how modern CPUs handle these operations. A single 32-bit integer fetch brings 32 primality flags into a register at once, improving spatial locality and reducing cache misses. Bitwise OR and AND operations are single-cycle instructions, making the test and set operations extremely fast. Furthermore, branch prediction and loop unrolling can be applied more effectively when working with packed words.

Bit Indexing and Mapping

Understanding the mapping is crucial for a bug-free implementation. For a full-range sieve where bit i corresponds to integer i, the word containing i is i // 32 and the bit position is i % 32. Using shifts, this is i >> 5 and i & 31. To test if i is prime, you check (bits[i >> 5] >> (i & 31)) & 1 == 0. To mark i as composite, you execute bits[i >> 5] |= 1 << (i & 31).

In the more common odd-only optimization, the mapping changes to save space. Only odd numbers are stored, so index i represents the number n = 2*i + 1. To map a number n to its bit index, you use i = n >> 1. The word is then (n >> 1) >> 5 or n >> 6, and the offset is (n >> 1) & 31. This halves the array size and also halves the number of marking operations, since even multiples can be skipped entirely by stepping by 2*p.

Marking Multiples Efficiently

When p is an odd prime, its odd multiples are p*p, p*p + 2*p, p*p + 4*p, .... Since we only store odds, we can iterate with step 2*p and mark only those positions. This avoids wasting time on even multiples that are not represented. Some highly optimized implementations also use wheel factorization, skipping multiples of 3 and 5 in addition to 2, but the odd-only bitwise sieve already captures the majority of the benefit with minimal complexity.

Implementation

Implementing a bitwise sieve in Python requires careful handling of Python's arbitrary-precision integers, which can act as bit arrays. While Python lists of ints are less memory-efficient than arrays in C, the bitwise technique still provides significant savings and serves as an excellent teaching model for bit manipulation. For true production performance in Python, the array('I') or bytearray with manual bit operations is often used, but using Python ints as bit words clearly demonstrates the principle.

The following implementation is a straightforward full-range bitwise sieve using 32-bit words. It is easy to understand and correctly handles all edge cases, making it ideal for learning the core mechanism before applying optimizations.

# Full-range bitwise sieve - stores all numbers 0..n
def bitwise_sieve_full(n):
    if n < 2:
        return []
    
    # Allocate bit array: one bit per number, 32 numbers per int
    size = (n >> 5) + 1  # Equivalent to (n // 32) + 1
    bits = [0] * size
    
    # Mark 0 and 1 as composite (not prime)
    # Bit 0 and 1 are in word 0
    bits[0] |= 1 << 0  # Mark 0
    bits[0] |= 1 << 1  # Mark 1
    
    # Sieve up to sqrt(n)
    limit = int(n ** 0.5) + 1
    for i in range(2, limit):
        # Test if i is prime: check if bit is 0
        if (bits[i >> 5] >> (i & 31)) & 1 == 0:
            # i is prime, mark all multiples starting from i*i
            start = i * i
            for j in range(start, n + 1, i):
                bits[j >> 5] |= 1 << (j & 31)
    
    # Collect primes by scanning bits
    primes = []
    for i in range(2, n + 1):
        if (bits[i >> 5] >> (i & 31)) & 1 == 0:
            primes.append(i)
    return primes

# Example usage
print(bitwise_sieve_full(30))
# Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]

This version is pedagogically clear but stores even numbers wastefully. The next implementation is the standard optimized version that stores only odd numbers, reducing memory by 50% and marking operations by nearly half. This is the variant you should use in interviews and performance-sensitive code.

# Optimized odd-only bitwise sieve - stores only odd numbers
def bitwise_sieve_odd(n):
    if n < 2:
        return []
    if n == 2:
        return [2]
    
    # Only store odd numbers: index i represents number 2*i + 1
    # We need to store odds up to n: count = (n // 2)
    size = (n >> 6) + 1  # (n//2)//32 + 1 = n//64 + 1
    bits = [0] * size
    
    # 1 is not prime, its index is 0 (since 2*0+1 = 1)
    bits[0] |= 1 << 0
    
    limit = int(n ** 0.5) + 1
    # Iterate only over odd numbers
    for i in range(3, limit, 2):
        # Map i to bit index: idx = i >> 1
        idx = i >> 1
        if (bits[idx >> 5] >> (idx & 31)) & 1 == 0:
            # i is prime, mark odd multiples: i*i, i*i+2*i, ...
            # i*i is odd, step is 2*i to stay on odds
            start = i * i
            step = i << 1  # 2 * i
            for j in range(start, n + 1, step):
                j_idx = j >> 1
                bits[j_idx >> 5] |= 1 << (j_idx & 31)
    
    # Collect results
    primes = [2]
    for i in range(3, n + 1, 2):
        idx = i >> 1
        if (bits[idx >> 5] >> (idx & 31)) & 1 == 0:
            primes.append(i)
    return primes

# Example: primes up to 100
print(bitwise_sieve_odd(100))
# Output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]

For even greater performance when n is very large, Python's bytearray can be used with precomputed bit masks. This approach is cache-friendly and leverages Python's optimized bytearray operations while still demonstrating bitwise logic.

import math

def bitwise_sieve_bytearray(n):
    """Memory-efficient sieve using bytearray and bit masks."""
    if n < 2:
        return []
    
    # Store only odds in a bytearray where each byte holds 8 odds
    # byte i holds odds: 2*(i*8 + k)+1 for k=0..7
    size = (n >> 4) + 1  # (n//2)//8 + 1 = n//16 + 1
    bits = bytearray(size)
    
    # Precomputed masks for speed
    masks = [1 << k for k in range(8)]
    
    # Mark 1 as composite: number 1 -> byte 0, bit 0
    bits[0] |= masks[0]
    
    limit = int(math.isqrt(n)) + 1
    for i in range(3, limit, 2):
        idx = i >> 1
        byte_idx = idx >> 3  # idx // 8
        bit_pos = idx & 7    # idx % 8
        if (bits[byte_idx] >> bit_pos) & 1 == 0:
            # Mark multiples
            start = i * i
            step = i << 1
            for j in range(start, n + 1, step):
                j_idx = j >> 1
                bits[j_idx >> 3] |= masks[j_idx & 7]
    
    primes = [2]
    for i in range(3, n + 1, 2):
        idx = i >> 1
        if (bits[idx >> 3] >> (idx & 7)) & 1 == 0:
            primes.append(i)
    return primes

# Benchmark helper - count primes up to 1M
def count_primes_bitwise(n):
    return len(bitwise_sieve_bytearray(n))

print(f"Primes up to 1000: {count_primes_bitwise(1000)}")  # 168

A reusable class-based design is often preferred for larger applications where you need to query primality multiple times without re-sieving. The following encapsulates the bit array and provides O(1) primality tests after an O(n log log n) preprocessing step.

class BitwisePrimeSieve:
    """Reusable bitwise sieve with O(1) is_prime queries."""
    def __init__(self, n):
        self.n = n
        self.size = (n >> 6) + 1
        self.bits = [0] * self.size
        self._sieve()
    
    def _sieve(self):
        if self.n < 2:
            return
        # Mark 1 as composite
        self.bits[0] |= 1 << 0
        limit = int(self.n ** 0.5) + 1
        for i in range(3, limit, 2):
            if not self.is_composite(i):
                step = i << 1
                start = i * i
                for j in range(start, self.n + 1, step):
                    self._mark(j)
    
    def _mark(self, num):
        idx = num >> 1
        self.bits[idx >> 5] |= 1 << (idx & 31)
    
    def is_composite(self, num):
        if num == 2:
            return False
        if num < 2 or (num & 1) == 0:
            return True
        idx = num >> 1
        return ((self.bits[idx >> 5] >> (idx & 31)) & 1) == 1
    
    def is_prime(self, num):
        if num > self.n:
            raise ValueError(f"Query {num} exceeds sieve limit {self.n}")
        return not self.is_composite(num)
    
    def primes(self):
        if self.n < 2:
            return []
        result = [2]
        for i in range(3, self.n + 1, 2):
            if not self.is_composite(i):
                result.append(i)
        return result

# Usage
sieve = BitwisePrimeSieve(50)
print(sieve.is_prime(29))  # True
print(sieve.is_prime(27))  # False
print(sieve.primes())

Step-by-Step Example

Let's walk through a concrete example of bitwise sieve prime numbers for n = 30 using the odd-only optimization. This will make the bit manipulations tangible. We will store only odd numbers, so our array represents numbers 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29. Index 0 corresponds to 1, index 1 to 3, index 2 to 5, and so on. The formula is number = 2*index + 1.

Initially, all bits are 0 (presumed prime) except index 0 (number 1) which we immediately mark as composite: bits[0] = 00000001 in binary (LSB is index 0). The limit for sieving is sqrt(30) ≈ 5.47, so we only need to process primes up to 5. We start with i = 3. We test its bit: index = 1, word = 0, offset = 1, bit is 0, so 3 is prime. We then mark its multiples starting from 3*3 = 9, stepping by 2*3 = 6: numbers 9, 15, 21, 27.

Marking 9: index = 4, word = 0, offset = 4, so we set bit 4. Marking 15: index = 7, offset = 7, set bit 7. Marking 21: index = 10, offset = 10, set bit 10. Marking 27: index = 13, offset = 13, set bit 13. After processing 3, our bit array's first word (covering indices 0-31) has bits 0, 4, 7, 10, 13 set.

Next, i = 5. We test index 2 (number 5): bit 2 is still 0, so 5 is prime. We mark multiples starting from 25, stepping by 10: numbers 25 only (since 35 exceeds 30). Marking 25: index = 12, offset = 12, set bit 12. Now bits 0, 4, 7, 10, 12, 13 are set. The next candidate would be i = 7, but 7 exceeds sqrt(30), so the marking phase is complete.

Finally, we collect primes by scanning all odd numbers and checking their bits. 3 (index 1) bit 1 is 0 → prime. 5 (index 2) bit 2 is 0 → prime. 7 (index 3) bit 3 is 0 → prime. 9 (index 4) bit 4 is 1 → composite. 11 (index 5) bit 5 is 0 → prime. 13 (index 6) bit 6 is 0 → prime. 15 (index 7) bit 7 is 1 → composite. Continuing this scan yields primes 3, 5, 7, 11, 13, 17, 19, 23, 29. Adding the special case 2 gives the complete list: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29. Notice how the bit array compactly encoded the entire sieve state in just a few integers.

Visual Bit State Table

The table below shows the bit state after each prime's marking pass for n=30. A 0 means presumed prime, 1 means marked composite.

Complexity Analysis

The time complexity of the bitwise sieve is identical to the classic Sieve of Eratosthenes, because the underlying mathematics does not change—only the storage mechanism does. The algorithm runs in O(n log log n) time, which is nearly linear and is considered optimal for enumerating all primes up to n. This complexity arises from the harmonic series over primes: the total number of marking operations is n * (1/2 + 1/3 + 1/5 + 1/7 + ...) which converges to n log log n by Mertens' theorem.

Best, average, and worst cases are essentially the same for the sieve, since the algorithm always performs the same marking pattern regardless of input distribution. There is no input-dependent branching that would cause variation. The only minor difference is the early exit for n < 2, which is O(1). For all n ≥ 2, the complexity is deterministic. This makes performance highly predictable, a valuable property for real-time systems.

Space complexity is where the bitwise sieve shines. A standard boolean sieve uses O(n) bytes (or O(n) booleans which may be larger in Python). The full-range bitwise sieve uses O(n/32) integers, which is O(n) asymptotically but with a 32x smaller constant factor. The odd-only variant uses O(n/64) integers, or O(n/16) bytes when using bytearray. This constant-factor reduction is critical in practice: for n = 10^9, a boolean array needs ~1 GB, while an odd-only 32-bit bitwise sieve needs ~15.6 MB, fitting easily in memory.

Cache performance also improves dramatically. Modern CPUs fetch memory in cache lines of 64 bytes. With a boolean array, each cache line holds 64 flags. With a bitwise array, each cache line holds 512 flags (64*8), meaning 8x fewer cache misses during both marking and scanning. This translates to real-world speedups of 2-4x even though Big O time is unchanged, because the hidden constant related to memory access is much lower.

When analyzing Python-specific performance, remember that Python loops add overhead. The theoretical O(n log log n) still holds, but the constant factor is higher than in C. For n up to 10^6, pure Python bitwise sieves are fast enough (under 0.5 seconds). For n up to 10^8, PyPy or CPython with numpy or array modules, or a PyPy JIT, is recommended. Alternatively, the marking loop can be vectorized using slicing or memoryviews for additional speed.

Variations and Optimizations

The basic bitwise sieve is just the starting point. Several powerful optimizations build upon it to push performance further. The most common is the odd-only storage already discussed, but more advanced techniques like wheel factorization, segmented sieving, and precomputed masks can yield additional gains.

Wheel factorization generalizes the odd-only idea. A 2-wheel skips evens (mod 2), a 2-3 wheel skips numbers divisible by 2 or 3 (saving 33% more), and a 2-3-5 wheel skips multiples of 2, 3, and 5 (saving 73% of numbers). In a bitwise context, this means your bit array only stores numbers coprime to the wheel base. For a 2-3 wheel, you store numbers congruent to 1 or 5 mod 6, requiring a more complex mapping but reducing memory to O(n/3). The tradeoff is increased code complexity for mapping and stepping, so wheels beyond 2-3-5 are rarely worthwhile.

Segmented bitwise sieve is essential for very large n where even the compressed bit array does not fit in cache or memory. Instead of sieving the entire range at once, it divides [2, n] into segments of size Δ (e.g., 32KB to fit in L1 cache). It first sieves primes up to sqrt(n) using a simple bitwise sieve, then uses those primes to mark each segment sequentially. Each segment's bit array is small and stays hot in cache, dramatically reducing cache misses. Space becomes O(√n + Δ) instead of O(n), allowing sieving up to 10^12 with modest memory.

Other micro-optimizations include using precomputed bit masks to avoid recomputing 1 << offset repeatedly, unrolling loops for small primes, and using memoryview or numpy for vectorized operations. In Python, using bytearray with memoryview allows the inner marking loop to be written in a way that the interpreter can optimize, and in PyPy the JIT can often unroll and vectorize the bit operations automatically.

Optimization Impact Summary

Choosing the right variation depends on your constraints. For interviews, the odd-only bitwise sieve hits the sweet spot of demonstrating bit manipulation without overcomplicating the code. For competitive programming where n ≤ 10^7, it is also sufficient. For systems programming or cryptography where n may be 10^9 or larger, segmented wheel sieves are the industry standard and are often implemented in C with intrinsics for maximum throughput.

Real-World Applications

Bitwise sieve prime numbers may seem like a niche academic optimization, but it appears in surprising places across modern infrastructure. Any system that needs many primes quickly and repeatedly benefits from the memory and cache advantages of bit packing.

In cryptography, RSA key generation requires finding large random primes. While RSA uses probabilistic tests like Miller-Rabin for 1024-bit primes, the initial trial division step often sieves small primes up to a few million to quickly eliminate composites before expensive tests. A bitwise sieve generates this small-prime table in milliseconds with minimal memory, accelerating key generation on embedded devices and smart cards where RAM is scarce. OpenSSL and similar libraries use bit-packed sieves for this pre-screening.

Web servers and databases use prime numbers for hash table sizing. To minimize collisions, hash tables are often resized to the next prime capacity. High-performance hash tables in systems like Redis, Memcached, and language runtimes (Python's dict, Java's HashMap) maintain a precomputed list of primes generated via a bitwise sieve at startup. The compact representation allows the prime table to stay resident in cache without evicting application data.

In networking, consistent hashing and load balancing algorithms sometimes use prime moduli to distribute keys uniformly. Content delivery networks and distributed databases precompute primes to configure sharding. Game engines and procedural generation also use primes for deterministic random number generation and for generating coprime step sizes in sampling algorithms.

Perhaps the most demanding application is scientific computing and number theory research. Projects like PrimeGrid and prime counting function computations (π(x) for large x) need to sieve up to 10^12 and beyond. Segmented bitwise sieves are the only feasible approach, as a full array would require terabytes. These implementations are heavily optimized in C/C++ but follow the exact bit-packing principles demonstrated in Python.

Application Requirements Table

Comparison with Alternatives

The bitwise sieve is one of several prime generation strategies, each with different tradeoffs. Understanding when to use it versus alternatives is crucial for system design and interviews.

The classic Sieve of Eratosthenes with a boolean array is the simplest to implement and fastest for small n (n < 10^6) due to minimal bit arithmetic overhead. However, it uses 8-32x more memory and suffers from poor cache behavior as n grows. It is ideal for quick scripts and teaching but not for large-scale production.

The Sieve of Sundaram and Sieve of Atkin are alternative sieving algorithms. Sundaram also eliminates evens but uses a different marking formula and is slightly slower in practice. Atkin has a theoretical O(n) time complexity and uses quadratic forms, but its constant factors and complex implementation make it slower than optimized Eratosthenes for n < 10^9, despite its better asymptotics. It also benefits from bit packing, but the underlying algorithm is harder to optimize.

Trial division—testing each number for divisibility by primes up to its square root—is the most memory-efficient (O(√n) to store primes) but has O(n√n) or O(n log n) time, making it orders of magnitude slower for enumerating all primes. It is only suitable when you need to test a few numbers for primality, not generate a range.

Probabilistic tests like Miller-Rabin and deterministic tests like AKS are primality tests for single large numbers, not sieves for ranges. They answer "is this one number prime?" for numbers with hundreds of digits, where sieving is impossible. They are complementary to sieves, not replacements.

In summary, choose the bitwise sieve when you need to generate all primes up to a large n with constrained memory and desire predictable performance. Choose trial division or Miller-Rabin when you only need to test isolated large numbers. For most practical range-generation tasks in Python, the odd-only bitwise sieve offers the best balance of speed, memory, and code clarity.

Common Mistakes and Best Practices

Even experienced developers introduce subtle bugs when implementing bitwise sieves. The most frequent mistake is incorrect bit indexing, especially off-by-one errors when mapping numbers to word and offset. For example, using i >> 5 for word and i & 32 instead of i & 31 for offset will silently produce wrong results. Always verify your mapping with small n and brute-force comparison. Another common error is forgetting that Python's 1 << 31 is fine, but 1 << 32 would overflow a 32-bit word conceptually—though Python ints are unbounded, the logic assumes 32-bit words, so offsets must stay 0-31.

Forgetting to handle 2 as a special case in odd-only sieves is another pitfall. Since 2 is not stored, loops that start at 3 and step by 2 must explicitly add 2 to the result. Similarly, marking must start at p*p, not 2*p, to avoid redundant work and to avoid marking the prime itself as composite. Starting at 2*p is correct logically but does O(n log n) work instead of O(n log log n), causing a significant slowdown for large n.

Integer overflow and shift width issues appear when porting Python logic to C. In C, 1 << 31 may overflow a signed 32-bit int, so you must use 1U << offset or 1ULL. In Python this is not an issue, but understanding it is important for interviews where the interviewer may ask about C implementation.

Best practices include: always use math.isqrt(n) instead of int(n**0.5) for accurate integer square roots, precompute masks or use constants for shifts, write helper functions is_set and set_bit to encapsulate bit logic and avoid duplication, and test against a known prime count (e.g., π(10^6) = 78498) to validate correctness. For performance, allocate the bit array as array('I') or bytearray rather than a Python list of ints if memory is critical, and consider using memoryview for faster access.

Pitfall Checklist

• Verify word = i >> 5 and offset = i & 31 for 32-bit packing, not 32 or 64.
• Explicitly handle n < 2 and prime 2 in odd-only implementations.
• Start marking at p*p, step by 2*p for odd-only to skip evens.
• Use unsigned shifts and masks to avoid sign-extension bugs in other languages.
• Test with small n (30, 100) and compare to brute force before scaling.
• Ensure sieve limit is inclusive: range(3, isqrt(n)+1, 2) not isqrt(n).

Finally, document your bit mapping clearly. A comment like "# bit i represents number 2*i+1" saves hours of debugging. When optimizing, profile before and after—sometimes the overhead of bit manipulation outweighs memory savings for n < 10^5, and a simple bytearray sieve may be faster in pure Python due to fewer Python-level operations.

Interview Questions

Bitwise sieve prime numbers is a favorite interview topic because it tests bit manipulation, algorithm optimization, and complexity analysis simultaneously. Below are common questions and how to approach them.

Q1: Implement a function that returns the count of primes up to n using O(n/64) memory.

This tests whether you can implement the odd-only bitwise sieve from scratch. The expected answer is to allocate (n>>6)+1 words, mark composites using bit operations, and count bits that remain 0. Emphasize handling edge cases, using isqrt, and explaining the mapping. Bonus points for mentioning that you only need to sieve up to sqrt(n) and for analyzing time O(n log log n) and space O(n/64).

Q2: How would you check if a single number x is prime after building a bitwise sieve up to n?

The answer is O(1) bit test: if x == 2 return True, if x is even return False, otherwise compute idx = x >> 1, word = idx >> 5, offset = idx & 31, and check (bits[word] >> offset) & 1 == 0. Discuss bounds checking (x > n requires error or extension) and why this is faster than trial division for repeated queries. This demonstrates understanding of preprocessing vs query tradeoffs.

Q3: Compare the memory usage of a boolean sieve vs a bitwise sieve for n = 10^9.

Calculate concretely: boolean sieve with Python list of bools uses ~1 byte per entry plus overhead, roughly 1 GB. With bytearray it's 1e9 bytes ~ 1 GB. Bitwise full-range uses 1e9/32 * 4 bytes ≈ 125 MB. Odd-only bitwise uses ~62.5 MB, or ~15.6 MB if using 64-bit words and odd-only. Explain cache implications and why the bitwise version fits in L3 cache while the boolean does not, leading to fewer cache misses and faster execution despite same Big O.

Q4: How would you extend the bitwise sieve to handle n = 10^12 where n does not fit in memory?

This probes knowledge of the segmented sieve. Answer: first generate primes up to 1e6 (sqrt(1e12)) using a bitwise sieve (~78k primes, tiny memory). Then divide the range [2, 1e12] into segments of size e.g., 1e6 or 32KB, and for each segment create a bit array for that interval, marking multiples of the base primes within the segment. Space is O(sqrt(n) + segment size), time remains O(n log log n). Mention bit packing within each segment for further savings and parallelization across segments.

Q5: What are the pitfalls of using 1 << offset in Python vs C for this sieve?

In Python, ints are arbitrary precision, so 1 << 31 or even 1 << 100 works correctly, though only offsets 0-31 are used for 32-bit words. In C, 1 << 31 overflows a 32-bit signed int (undefined behavior), so you must use 1U << offset or 1ULL and ensure the array type is uint32_t or uint64_t. Also discuss endianness and portability, and why Python's abstraction hides these low-level details but understanding them is crucial for systems roles.

Preparing for these questions involves not just memorizing code but understanding the why: why bit packing helps cache, why odd-only is the best tradeoff, and why segmented sieving is needed for huge n. Practice writing the sieve on a whiteboard without an IDE, focusing on clean helper functions and clear comments about the bit mapping.