Creating a compact mapping from an integer $n$ to its primality up to a limit $N$ involves efficiently determining whether each number in a given range is a prime number. The most widely-known algorithm for this task is the Sieve of Eratosthenes, which provides a compact way to determine prime numbers up to $N$. To implement this efficiently, you must understand algorithmic optimization and space reduction techniques.

Sieve of Eratosthenes

The Sieve of Eratosthenes is a simple and ancient algorithm used to find all prime numbers up to a particular integer. It operates with a time complexity of $O(N \log \log N)$ and requires $O(N)$ space. Here's how it works:

1. Initialization: Create a boolean array is_prime of size $N + 1$ and initialize all entries as true. Array index represents numbers from $0$ to $N$. Set is_prime[0] and is_prime[1] to false, since $0$ and $1$ are not prime.
2. Iterate through Numbers: Starting from the first prime number, $2$, iterate over each number up to $\sqrt{N}$. For each number $i$ that is marked as true in is_prime, mark all of its multiples (from $i^2$ to $N$) as false.
3. Extract Primes: After processing the array, the indices which remain true indicate that the number is prime.

Implementation Example

Here's a sample implementation in Python:

1def sieve_of_eratosthenes(N):
2    is_prime = [True] * (N + 1)
3    is_prime[0], is_prime[1] = False, False
4    
5    for i in range(2, int(N**0.5) + 1):
6        if is_prime[i]:
7            for j in range(i * i, N + 1, i):
8                is_prime[j] = False
9    
10    return {i: is_prime[i] for i in range(N + 1)}
11
12# Example usage:
13N = 50
14prime_mapping = sieve_of_eratosthenes(N)
15print(prime_mapping)

This code creates a dictionary mapping each integer to a boolean indicating its primality. The space used is linear relative to $N$.

Optimizations

While the Sieve of Eratosthenes is efficient, several optimizations can be applied to make the mapping more compact:

1. Memory reduction:
   • Bit Arrays: Instead of storing a boolean value in a full-byte or an integer array, utilize a bit array (bitset) to reduce memory usage by a factor of 8. This approach is especially useful in languages that support bit manipulation.
2. Segmented Sieve: For very large values of $N$, applying a basic sieve may be impractical due to memory constraints. A segmented sieve works by dividing the range into smaller segments and applying the sieve to each segment independently, drastically reducing memory requirements. This maintains the efficient time complexity while enabling the processing of larger ranges.
3. Wheel Factorization: This technique involves skipping numbers known to be non-prime candidates, such as even numbers or numbers divisible by 3, 5, etc. By skipping these, you reduce the number of iterations and unnecessary operations, thus enhancing efficiency.

Advantages and Trade-offs

• Time Complexity: All the optimizations strive to keep the time complexity at or near $O(N \log \log N)$ while trading off complexity and memory usage.
• Space Complexity: The primary goal of these optimizations is to reduce the space needed, particularly for large values of $N$.

Conclusion

Creating a compact mapping of $n \rightarrow$ isprime(n) up to a limit $N$ demands efficient use of space and time. Though the Sieve of Eratosthenes provides a fundamental approach, employing strategies like bit arrays, segmented sieves, and wheel factorization can significantly enhance performance. When handling enormous data sets, consider the trade-offs between complexity, execution time, and memory consumption to ensure the best solution for your scenario.