How to create the most compact mapping n → isprime(n) up to a limit N?

The fastest algorithm for general prime testing is AKS. The Wikipedia article describes it at lengths and links to the original paper.

If you want to find big numbers, look into primes that have special forms like Mersenne primes.

The algorithm I usually implement (easy to understand and code) is as follows (in Python):

def isprime(n):
    """Returns True if n is prime."""
    if n == 2:
        return True
    if n == 3:
        return True
    if n % 2 == 0:
        return False
    if n % 3 == 0:
        return False

    i = 5
    w = 2

    while i * i <= n:
        if n % i == 0:
            return False

        i += w
        w = 6 - w

    return True

It’s a variant of the classic O(sqrt(N)) algorithm. It uses the fact that a prime (except 2 and 3) is of form 6k - 1 or 6k + 1 and looks only at divisors of this form.

Sometimes, If I really want speed and the range is limited, I implement a pseudo-prime test based on Fermat’s little theorem. If I really want more speed (i.e. avoid O(sqrt(N)) algorithm altogether), I precompute the false positives (see Carmichael numbers) and do a binary search. This is by far the fastest test I’ve ever implemented, the only drawback is that the range is limited.