from IPython.display import display
from IPython.display import HTML

def isPrime(x):
    if (x==1):
        return False
    for i in range(2,x):
        if x%i==0:
            return False
    return True

def getPrimes(maxValue):
    primes = []
    for i in range(1,maxValue):
        if isPrime(i):
            primes.append(i)
    return primes

primes = getPrimes(10000)

%%timeit
getPrimes(10000)

len(primes)

def showState(l, p, nx):
    numbers = ''
    for n in l:
        style=''
        if n<0:
            style+='text-decoration: line-through; background-color: rgb(171, 231, 255);'
        if n==p:
            style+='background-color: rgb(230,255,95);'
        if n==nx:
            style+='background-color: rgb(150, 233, 150);'
        if n==0:
            style+='background-color: rgb(220,220,220); color: rgb(220,220,220);'    
        numbers+='<td style="color: rgb(50,50,50); padding:0; width:1.5em; border-color: rgb(240,240,240); text-align:center;{0}">{1}</td>'.format(style, abs(n))
    s = """<table style='font-size: 12px; height:0.7em; '>
    <tr style="height: 0.7em;"'>{0}</tr></table>""".format(numbers)
    h = HTML(s)
    display(h)
    

def sieve(size, showStates=True):
    l = list(range(2,size+1)) #generate the candidate set
    idx = lambda x: x-2 #just a simple mapping from number in list to list index
    p = 2 #seed with initial prime
    
    for iteration in range(len(l)):
        #mark every multiple of p
        for i in range(p*2, size+1, p):
            l[idx(i)] = -i
                
        #find the next unmarked value, that's the next p
        nextPrime = 0
        for i in l[idx(p+1):]:
            if i>0:
                nextPrime = i
                break
        
        if (showStates):
            showState(l, p, nextPrime)
            for i in range(p*2, size+1, p):
                l[idx(i)] = 0
                
        p = nextPrime
        
        #if we haven't found any unmarked values, we're done
        if p == 0:
            break
            
    #return all unmarked values    
    return filter(lambda x: x>0, l)

sieve(58, True)

%%timeit
v = sieve(10000, False)

len(sieve(10000, False))

#comments removed for brevity
def sieve(size, showStates=True):
    l = list(range(2,size+1)) 
    idx = lambda x: x-2 
    p = 2 
    for iteration in range(int(0.5+len(l)**0.5)):
        #mark every multiple of p up to sqrt(n)
        for i in range(p*2, size+1, p):
            l[idx(i)] = -i
        nextPrime = 0
        for i in l[idx(p+1):]:
            if i>0:
                nextPrime = i
                break
        if (showStates):
            showState(l, p, nextPrime)
            for i in range(p*2, size+1, p):
                l[idx(i)] = 0
        p = nextPrime
        if p == 0:
            break
    return filter(lambda x: x>0, l)

%%timeit
v = sieve(10000, False)

def maxPrime(n):
    return int(0.5+(float(n)*log(n)+ n*log(log(n))))
    
limit = maxPrime(10000)
print('The 10000th prime has a value < {0}'.format(limit))

primes = sieve(limit, False)
len(primes)

primes[10000]

source = '''
73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450
'''.replace('\n','')

#break the source string into a series of 13 character long slices at every possible position
window_size = 13
slices = [source[x:x+window_size] for x in range(len(source) - window_size + 1)]

#compute the product of each slice
products = [product(map(int, row), dtype='int64') for row in slices]

max(products)