Permutable Primes

pprimes.py

#!/usr/bin/env python3
# Or python2 

import itertools
import collections

# @profile
def get_primes(nMax):
    """Return a set of prime numbers under nMax

    Starts at 2

    On my computer, first million primes in 2.19s
    """
    # Python doesn't have an OrderedSet type,
    # so OrderedDict's keys will have to work
    numbers = collections.OrderedDict.fromkeys(range(2, nMax))
    # Sieve method to find all primes
    primes = set()
    while numbers:
        p = numbers.popitem(last=False)[0]
        primes.add(p)
        for x in range(p*2, nMax+1, p):
            numbers.pop(x, None)
    return primes


# @profile
def get_primes2(nMax):
    """Return a set of prime numbers under nMax

    On my computer, first million primes in 0.515s
    """
    numbers = range(3, nMax, 2)
    snumbers = set(numbers)
    primes = set((1,2))
    for p in numbers:
        if p not in snumbers:
            continue
        primes.add(p)
        snumbers -= set(range(p*2, nMax+1, p))
    return primes


# @profile
def find_primePerm(nMax):
    primes = get_primes2(nMax)
    primelist = list(primes)
    primelist.sort()
    ppprimes = primes.copy()  # Possible permutable primes
    pcounts = collections.OrderedDict()  # Permutation counts
    lenmax = 0  # Record the max number of permutations so we don't have to look it up later
    # For each possible prime
    for p in primelist:
        if p not in ppprimes:
            continue
        permutations = set(int("".join(x)) for x in itertools.permutations(str(p)) if x[0] != "0")
        # Get permutable primes
        pprimes = permutations & primes
        # Record the number of permutable primes
        if len(pprimes) >= 2:
            pcounts[p] = len(pprimes) - 1
            lenmax = max(lenmax, len(pprimes) - 1)
        # Remove permutations from our remaining primes to test
        ppprimes -= pprimes
    # Only return the ones tied for maximum permutable primes
    maxpcounts = [[k,v] for k,v in pcounts.items() if v == lenmax]
    return maxpcounts
        
if __name__ == '__main__':
    find_primePerm(1000000)
    # get_primes(1000000)
    # get_primes2(1000000)