Problem 5

import time

#breaks down numbers into there prime factorization
def recursiveFactorizer(toFactor, primeFactorList, primeList):

    #simplifies the information that is needed for easy access
    factorizationProduct = listProduct(primeFactorList)
    revisedToFactor = toFactor/factorizationProduct
    lastNumberInList = primeList[int(primeList.__len__()-1)]

    #checks if all the factors have been found
    if revisedToFactor == 1:
        return primeFactorList

    #checks if there is multiple occurences of a prime factor
    if revisedToFactor%lastNumberInList == 0:
        primeFactorList.append(lastNumberInList)
        return recursiveFactorizer(toFactor, primeFactorList, primeList)

    #generates primes and checks if they are factors of the adjusted number to factor
    for number in range(lastNumberInList, int(revisedToFactor)+1):
        isFactor = True
        for prime in primeList:
            if number%prime == 0:
                isFactor = False
                break
        if isFactor:
            primeList.append(number)
            if revisedToFactor%number == 0:
                primeFactorList.append(number)
                #calls the function on the updated primeFactorList and primeList
                return recursiveFactorizer(toFactor, primeFactorList, primeList)

#finds the product of all the elements in a list
def listProduct(list):
    finalProduct = 1
    for number in list:
        finalProduct *= number
    return finalProduct

#finds the set of primes that compose the least common multiple of these two sets
def multipleFinder(primeListOrig, primeList):
    newPrimeList = primeListOrig
    #runs through all numbers in the new list and adds to
    #original if not present in correct frequency
    for number in primeList:
        if primeList.count(number) > newPrimeList.count(number):
            amountDifference = primeList.count(number) > newPrimeList.count(number)
            for amount in range(amountDifference):
                newPrimeList.append(number)
    return newPrimeList

#finds the least common multiple of a set of numbers
def findLeastCommonMultiple(listOfNumbers):
    totalPrimeList = []
    for number in listOfNumbers:
        primeList = [2]
        primeFactorList = []
        primeFactorization = recursiveFactorizer(number, primeFactorList, primeList)
        multipleFinder(totalPrimeList, primeFactorization)
    return totalPrimeList


#main
#starts the timer
start = time.time()
#generate a list of the numbers that need to be factors of a greater number
listOfNumbers = []
for i in range(1,20):
    listOfNumbers.append(i)
#find the least common multiple
leastCommonMultiple = listProduct(findLeastCommonMultiple(listOfNumbers))
#ends timer
end = time.time()
print("Time: " + str(end-start))
print("LCM: " + str(leastCommonMultiple))