def slowPrimeDigits(maxValue):
    """ Very slow way to make a list of primes
    Start a list, then remove each number that is a prime times n
    Slow as removing an item from a list means moving every element above it
    """
    # make an array to hold each number up to maxValue
    primes = []
    # fill the array
    for i in range(maxValue):
        primes.append(i)
    # zero and one are not prime
    primes.remove(0)
    primes.remove(1)
    # now apply Sieve of Eratosthenes (google it...)
    for i in primes:
        # make a list of all factors of i (next prime)
        factors = range(i, maxValue, i)
        # first factor is prime (it stays) the rest are removed
        for f in factors[1:]:
            # check if f is still in primes
            if f in primes:
                # if so remove from 
                primes.remove(f)
    # output
    return primes


def primeDigits(maxValue):
    """Faster version of the code, uses fixed length arrays instead of variable lists"""
    # make an array to hold each number up to maxValue
    primes = []
    # fill the array
    for i in range(maxValue):
        primes.append(i)
    # now eliminate non-prime numbers
    primes[0] = -1 # zero is not a prime
    primes[1] = -1 # nor is one 
    i=2 # first prime is two at index = 2 
    while ( i<len(primes) ):
        prime = primes[i] # this is a prime number
        factor = prime + prime # prime*2 is not prime 
        while ( factor < len(primes) ):
            primes[factor] = -1
            factor += prime # next prime
        i+=1
        while( i < len(primes) and primes[i] == -1 ):
            i+=1
    # output
    return [p for p in primes if p>-1]

def fasterPrimeDigits(maxValue):
    """Use fixed length array of booleans to make list more compact"""
    # make an array to hold each number up to maxValue
    primes = [True] * maxValue
    # now eliminate non-prime numbers
    primes[0] = False # zero is not a prime
    primes[1] = False # nor is one 
    i=2 # first prime is two at index = 2 
    # use xrange below if python2
    for i in range(2,maxValue):
        if( not primes[i] ):
            continue # already know this is not a prime
        # use xrange below if python2
        for factor in range(i*i, maxValue, i):
            # so lowest factor not already excluded is p^2
            # in steps of p to end of list eliminate factors
            primes[factor] = False
    # output
    # use xrange below if python2
    return [i for i in range(maxValue) if primes[i]]

import numpy
def primeDigitsNumPy(maxValue):
    """Using numpy array of booleans instead of integers, 
    numpy uses much faster routines to process fixed length arrays"""
    isPrime = numpy.ones(maxValue,dtype=numpy.bool)
    isPrime[0] = isPrime[1] = False
    # use xrange below if python2
    for p in range(2, int(numpy.sqrt(maxValue))+1):
        if isPrime[p]:
            for z in range(2*p, maxValue, p):
                isPrime[z] = False
    primes = numpy.where(isPrime)[0] # see docs for how this works
    # primes is not a list it is a numpy.ndarray, so convert to match 
    # other functions
    return list(primes)

def fastestPrimeDigitsNumPy(maxValue):
    """Using numpy array of booleans instead of integers, 
    careful loop choice to avoid repeating known values"""
    isPrime = numpy.ones(maxValue, dtype=numpy.bool)
    isPrime[0] = isPrime[1] = False # 0 & 1 not prime
    # use xrange below if python2
    for p in range(2, int(numpy.sqrt(maxValue)) + 1):
        if isPrime[p]: 
            isPrime[p*p::p] = False # implicit loop...
            # index p*p -> max in steps of p
            # Started from p^2 as smaller primes already done
    primes = isPrime.nonzero()[0]
    return primes.tolist()

def fastestPrimeDigitsNumPy2(maxValue):
    """Using numpy array of booleans instead of integers
    only consider odd numbers as all even (except 2) prime"""
    isPrime = numpy.ones(maxValue // 2, dtype=numpy.bool)
    # use xrange if using python2
    for p in range(3, int(numpy.sqrt(maxValue)) + 1, 2):
        if isPrime[p // 2]: 
            isPrime[p*p // 2::p] = False
    primes = 2 * isPrime.nonzero()[0] + 1
    primes[0] = 2 # have to add 2 back as exlcuded above
    return primes.tolist()


import profile

# set maxmimum value
# for the "slow" code only do up to 10k in <1s
max10k = 10000
sumOfPrimes10k = 5736396

# for fast code can do up to 1M in <1s 
max1M = 1000000
sumOfPrimes1M = 37550402023


# timeit runs repeated loops on a line to check how fast it is
# check output is what we expect...
print("\nTest with \ntimeit if(numpy.sum(slowPrimeDigits(max10k)) != sumOfPrimes10k): print('Code failed')")
print(" and ")
print("timeit if(numpy.sum(primeDigits(max10k)) != sumOfPrimes10k): print('Code failed')")
print("timeit if(numpy.sum(primeDigitsNumPy(max10k)) != sumOfPrimes10k): print('Code failed')")
print("timeit if(numpy.sum(fastestPrimeDigitsNumPy(max10k)) != sumOfPrimes10k): print('Code failed')")
print("timeit if(numpy.sum(fastestPrimeDigitsNumPy2(max10k)) != sumOfPrimes10k): print('Code failed')")