Common python functions

common.py

def isPrime(n):
    """ All primes number greater than 3 can be expressed in the form 6k +/- 1 """
    if n <= 0 or n == 1:
        return False
    elif n < 4: # Handle 2 and 3
        return True
    elif n%2==0:
        return False
    elif n < 9: # 4,6,8 are already excluded
        return True
    elif n%3==0:
        return False
    else:
        r = int(n**.5)
        f=5
        while f <= r:
            if n%f == 0:
                return False
            elif n%(f+2) == 0:
                return False
            f+=6
        return True
        
def primeFactors(n):
    """ Each number can be written under the form: p1^a1*p2^a2*...*pn^an """
    """ Return the list of Pn and An """
    L=[] # primes factors (p)
    M=[] # number of each factors (a)
    if n%2==0:
        count = 1
        L.append(2)
        n=n // 2
        while n % 2 == 0:
            n=n // 2
            count += 1
        M.append(count)
    factor = 3
    maxFactor = n**.5
    while n>1 and factor <= maxFactor:
        if n % factor == 0:
            count = 1
            n=n // factor
            L.append(factor)
            while n % factor == 0:
                n=n // factor
                count += 1
            M.append(count)
            maxFactor = n**.5
        factor = factor + 2
    if n!=1:
        L.append(n)
        M.append(1)
    return L,M
        
def eratosthene(n):
    """ Return a list of all prime numbers lower or equal to n """
    if n < 2:
        return []
    elif n == 2:
        return [2]
        
    L = [False, False, True] + [True, False]*((n//2) - 1 + n%2)
    L[2] = True
    primes = [2]
    
    root = int(n**.5)
    # root must be odd
    root += 1 - root%2
    for i in range(3, root+1, 2):
        if L[i]:
            primes.append(i)
            L[i::i] = [False]*((len(L)-i)//i + int((len(L)-i)%i>0))
        
    # Now all remaining numbers are prime
    for i in range(root, len(L)-1, 2):
        if L[i]:
            primes.append(i)
        
    return primes    

def factorial(n):
    if n == 0 or n == 1:
        return 1

    s = 1
    for i in range(1,n+1):
        s *= i
    return s 

def digits(n):
    if n == 0:
        return [0]
    L = []
    while n != 0:
        L.insert(0, n%10)
        n = n//10
    return L

def numberFromDigits(L):
    n = 0
    for i in range(len(L)):
        n += L[i]*10**(len(L)-1-i)
    return n
    
def isPandigital(digits, start=1, stop=9):
    """ Given a list of digits check if the number is pandigital """
    """ ie: contains all digits from <start> to <stop>"""
        
    if start >= stop or stop > 9 or len(digits) != stop-start+1:
        return False
        
    L = digits[:]
    L.sort()
    for i in range(len(L)):
        if L[i] != i+start:
            return False
    return True
    
def circularRotation(L):
    """ return all rotation of the list """
    """ example: input = [a,b,c] --> output = [[a,b,c], [b,c,a], [c,a,b]] """
    L2 = L[:]
    out = []
    out.append(L2)
    for i in range(len(L)-1):
        new = L2[1:]
        new.append(L2[0])
        L2 = new
        out.append(L2)
        
    return out