Playing with Primes in Python

gistfile1.py

import math
import random

class PrimeBuilder:
  _p = set()
  _maxChecked = 0

  def __init__(self, p = {2, 3, 5}):
    self._p = p
    self._maxChecked = max(p)

  def _appendPrimes(self, x):
    x = int(x)
    if x <= self._maxChecked:
      pass
    else:
      for i in range(self._maxChecked + 1, x + 1):
        hasPrimeFactor = False
        for p in sorted(self._p): # sort should improve branch prediction
          if p <= math.sqrt(i) and i%p == 0:
            hasPrimeFactor = True
            break

        if not hasPrimeFactor:
          self._p.add(i)

      self._maxChecked = x

  def getPrimes(self, x):
    """Check to see if x is prime"""
    self._appendPrimes(x)
    return {p for p in self._p if p <= x}

class Naturals:
  _P = PrimeBuilder()

  def isPrime(self, x):
    return x in self._P.getPrimes(x)

  def primeFactors(self, x):
    """Prime factors of x"""
    factors = set() 
    for p in self._P.getPrimes(math.sqrt(x)):
      if x%p == 0:
        factors |= self.primeFactors(x//p) | {p}

    # If x is prime
    if len(factors) == 0:
      factors.add(x)
      _ = self._P.getPrimes(x)

    return factors

  def primeFactorise(self, x):
    """Prime factorisation of x"""
    factorisation = {}

    for p in self.primeFactors(x):
      if p == 1:
        factorisation = {1:1}
      else:
        i = 1
        while x / (p**i) == x // (p**i):
          i += 1
        factorisation[p] = i - 1

    return factorisation

  def isHamming(self, x, t = 5):
    """Highest prime factor of x is <= t"""
    if x <= t:
      return True
    else:
      return max(self.primeFactors(x)) <= t

def prettyFactorisation(factorisation):
  """Pretty prints factorisation dictionary"""
  output = ''
  for p in sorted(factorisation):
    if len(output) > 0:
      output += ' * '
    output += str(p)
    if factorisation[p] > 1:
      output += '^' + str(factorisation[p])

  return output

N = Naturals()

print(N.isPrime(1))                                        # False
print(N.isPrime(5))                                        # True
print(N.isPrime(27))                                       # False
print(N.primeFactors(30030))                               # {2, 3, 5, 7, 11, 13}
print(N.primeFactors(28))                                  # {2, 7}
print({i for i in range(1,16) if N.isHamming(i)})          # {1, 2, 3, 4, 5, 6, 8, 9, 10, 12, 15}

n = random.randint(1,1000)
print(n, "=", prettyFactorisation(N.primeFactorise(n)))