Trial Division faster than Sieve for Primality Test?

Question

I wrote two primality tests in python. First one is based on trial division, the second one applies sieve of Eratosthenes. My understanding is that sieve should have a smaller time complexity than trial, so sieve should be asymptotically faster.

However when I run it, trial division is much faster. For example, when n = 6*(10**11), is_prime(n) takes less than a second, but is_prime_sieve(n) practically never ends! Did I wrote the sieve wrong?

My code is:

# determines if prime using trial division
def is_prime(n):
    d = {}
    u = math.floor(math.sqrt(n))
    i = 2
    # trial division: works pretty well for determining 600 billion
    while (i <= u):
        if (n % i == 0):
            return False
        i += 1
    return True

# primality test with sieve
def is_prime_sieve(n):
    # first find all prime numbers from 2 to u
    # then test them
    u = math.floor(math.sqrt(n))
    prime = {}
    lst = range(2, int(u)+1)
    for i in lst:
        j = 2
        prime[i] = True
        while (i*j <= u):
            prime[i*j] = False
            j += 1
    while (u >= 2):
        if (u not in prime) or (prime[u]):
            if (n % u == 0):
                return False
        u -= 1
    return True

Answer 1

For the Sieve of Erastothenes you are recomputing the sieve every time. The sieve should be cached so that you only generate it once. It works well when you build the sieve once and then perform many primality checks; it is very inefficient if you only check a single number.

This means, by the way, that you need to anticipate the highest prime number and generate the sieve table up to that number.

When done right, is_prime_sieve becomes simply:

def is_prime_sieve(n):
    return prime[n]

You would not need the while loop.