Primes for stackexchange

def isprime(n, smallprimes):
    """Checks if n is prime.

    smallprimes should be the SORTED list of all primes,
    including all that are <= square root of p"""

    for p in smallprimes:
        if p*p > n:
            return True
        if n % p == 0:
            return False


    return True
# Nice test case: isprime(2, [2])

def primes_up_to(m):
    primes = []

    for n in xrange(2, m+1):
        if isprime(n, primes):
            primes.append(n)

    return primes

def range_sieve(lo, hi, smallprimes):
    """Finds all primes p with lo <= p <= hi. smallprimes is as in 'isprime'

    hi & lo might be large, but hi-lo+1 miust fit into a long"""

    # So ugly! But SO FAST!! How??

    delta = hi-lo+1
    iamprime = [True] * delta      # iamprime[i] says whether lo + i is prime
    if lo<= 1:
        iamprime[1 - lo] = False

    def sillyfun():      # For profiling & speed comparison
        pass

    for p in smallprimes:
        rem = lo % p
        if rem == 0:
            iamprime[0] = False
        for i in xrange(p - rem, delta, p):
            iamprime[i] = False
            sillyfun()

        if p >= lo and p <= hi:
            iamprime[p - lo] = True

    return [p + lo for (p, ami) in enumerate(iamprime) if ami]

def range_f1(lo, hi, smallprimes):
    """Finds all primes p with lo <= p <= hi. smallprimes is as in 'isprime'

    hi & lo might be large, but hi-lo+1 miust fit into a long.
    Does not use a function call to check prime-ness, twice as fast"""

    primes =[]
    for i in xrange(hi-lo+1):
        n = lo + i

        isprime = True
        for p in smallprimes:
            if n % p == 0:
                isprime = False
                break

        if isprime:
            primes.append(n)

    return primes

def range_f2(lo, hi, smallprimes):
    """Finds all primes p with lo <= p <= hi. smallprimes is as in 'isprime'

    hi & lo might be large, but hi-lo+1 must fit into a long.
    Why so slow?"""

    primes =[]
    for i in xrange(hi-lo+1):
        n = lo + i

        try:
            (1 for p in smallprimes if n % p ==0).next()
        except StopIteration:
            primes.append(n)

    return primes

if __name__ == "__main__":
  from cProfile import run as prof
  from math import sqrt

  N = 10 ** 9
  rtN = int(sqrt(N))
  delta = 10**5
  sp=primes_up_to(rtN)

# len sp = 3401
#range_**(N-delta,N,sp) should have 4832 elmts