def sieve_for_primes_to(n):
    size = n//2
    sieve = [1]*size
    limit = int(n**0.5)
    for i in range(1,limit):
        if sieve[i]:
            val = 2*i+1
            tmp = ((size-1) - i)//val 
            sieve[i+val::val] = [0]*tmp
    return [2] + [i*2+1 for i, v in enumerate(sieve) if v and i>0]

sieve = sieve_for_primes_to(1000000)


primesixes = {}
maxprime = 0
maxsixes = 0
for prime in sieve:
    if prime >= 100000:
        sixes = str(prime).count('6')
        primesixes[prime] = sixes
        if sixes > maxsixes:
            maxsixes = sixes
            maxprime = prime
            print("New max", prime, sixes)