#By Jacob Ford

import time

def isPrime(n): #returns true or false
    if n <= 1:
        return False
    elif n == 2:
        return True
    for z in [2] + range(3,n,2):
        if n % z == 0:
            return False
    return True

def primes(n): #returns list of unique prime factors in ascending order
    if n == 2:
        return [2]
    divisor = 2
    primeFactors = []
    endLoop = n/2+1
    while divisor <= endLoop:
        if n % divisor == 0:
            n = n / divisor
            if isPrime(divisor) and divisor not in primeFactors:
                primeFactors += [divisor]
            endLoop = n / divisor + 1
            divisor = 2
        else:
            divisor += 1
    if n != 1 and n not in primeFactors:
        primeFactors += [n]
    return primeFactors

def Q(n):
    if n == 0:
        return 2
    elif n > 1:
        return primes(n)[0]

def L(m,n):
    if n == 1:
        return 1
    m = float(m)
    primeFactors = primes(n)
    if primeFactors[0]<=m:
        return 0
    else:
        product = n
        for z in primeFactors:
            product *= (1-m/z)
        return int(round(product))

def R(m,n): #returns tuple (Q,L,R,H (m,n))
    iterations = 1 #to fit with the document, this starts at 1, not 0
    L1 = L(m,n)
    Q1 = Q(n)
    n = L1
    while n >= 2:
        n = L(m,n)
        iterations += 1
    return Q1,L1,iterations,n
    
def output():
    divider = "#############################################"
    print "Enter a value for m and hit enter."
    m = int(raw_input('m = '))
    print "Enter a starting value."
    low = int(raw_input('lowest value of n = '))
    print "Enter the value you want to calculate up to."
    high = int(raw_input('highest value of n = '))
    #print "For the following questions, type 0 for no or 1 for yes."
    #q = input('Do you want the output to include Q(n)?')
    #l = input('Do you want the output to include Lm(n)?')
    #r = input('Do you want the output to include Rm(n)?')
    #h = input('Do you want the output to include Hm(n)?')
    qList = []
    lList = []
    rList = []
    hList = []
    start = time.clock()
    for z in range(low,high+1):
        output = R(m,z)
        qList += [output[0]]
        lList += [output[1]]
        rList += [output[2]]
        hList += [output[3]]

    print
    print "Q(n):"
    print
    for z in qList:
        print z
    print
    for z in range(4):
        print divider
    print
    print "L(m,n):"
    print
    for z in lList:
        print z
    print
    for z in range(4):
        print divider
    print
    print "R(m,n):"
    print
    for z in rList:
        print z
    print
    for z in range(4):
        print divider
    print
    print "H(m,n):"
    print
    for z in hList:
        print z
    elapsed = (time.clock() - start)
    
    #print elapsed,'seconds taken' #remove the first '#' to see time taken

while(True):
    output()
    print
    print "Enter 1 to do more calculations"
    cont = raw_input("Continue? ")
    if cont != '1':
        break

#timing (for m = 2):

# 1 - 100 : 0.854943315778 seconds taken
# 1 - 500 : 4.28940875281 seconds taken
# 1 - 2500: 19.9785490368 seconds taken