How to solve largest prime factor problem?

Description of the problem: The prime factors of 13195 are 5, 7, 13 and 29.What is the largest prime factor of the number 600851475143 ?

Solution: Beginner Level

The basic solution is created without any functions or classes. First the given example (prime factors of 13195) will be confirmed and then the largest prime factor of the number 600851475143 will be found.

The prime factors of 13195 are 5, 7, 13, and 29

The first step is to ask user to type in the number for which we want to find prime factors. This will be done using the input function that will return the string. If we want to use this nubmer we have to convert it to integer so we have to use int function.

n = int(input("Enter a number> "))

The second step is to generate the list of prime nubmers.

primNumbers = [i for i in range(2, 10000+1) if 0 not in [i%n for n in range(2,i)]]

The prime factors that are found have to be stored in the list, so we will create an empty list that will be assigned to PrimeFactors variable.

PrimeFactors = []

The next step is to create a loop in which the prime numbers will be used in division with number that user typed in. If the division between n and the prime number is without remainder than the prime number will be appended into prime factors list. If however the remainder exists that the prime number will be skipped. At the end of each iteration the value of variable n will be lowered will be equal to the result of previous division of number n with the prime number and iteration number will be updated.

i = 0
while i < len(primNumbers):
    if n%primNumbers[i] == 0:
        print("{}/{} = {}".format(n, primNumbers[i], n/primNumbers[i]))
        PrimeFactors.append(primNumbers[i])
        n = n/primNumbers[i]
    elif n/primNumbers[i] == 1.0:
        break
    i+=1

Now we will show the list of prime factors.

print("PrimeFactors = {}".format(PrimeFactors))

To find the largest prime number we will use the max function.

print("Largest prime factor = {}".format(max(PrimeFactors))

n = int(input("Enter a number> "))
primNumbers = [i for i in range(2, 10000+1) if 0 not in [i%n for n in range(2,i)]]
PrimeFactors = []
i = 0
while i < len(primNumbers):
    if n%primNumbers[i] == 0:
        print("{}/{} = {}".format(n, primNumbers[i], n/primNumbers[i]))
        PrimeFactors.append(primNumbers[i])
        n = n/primNumbers[i]
    elif n/primNumbers[i] == 1.0:
        break 
    i+=1
print("PrimeFactors = {}".format(PrimeFactors))
print("Largest prime factor = {}".format(max(PrimeFactors)))

Output:

Enter a number> 13195
13195/5 = 2639.0
2639.0/7 = 377.0
377.0/13 = 29.0
29.0/29 = 1.0
PrimeFactors = [5, 7, 13, 29]
Largest prime factor = 29

Largest Prime Factor of the number 600851475143?

n = int(input("Enter a number> "))
primNumbers = [i for i in range(2, 10000+1) if 0 not in [i%n for n in range(2,i)]]
PrimeFactors = []
i = 0
while i < len(primNumbers):
    if n%primNumbers[i] == 0:
        print("{}/{} = {}".format(n, primNumbers[i], n/primNumbers[i]))
        PrimeFactors.append(primNumbers[i])
        n = n/primNumbers[i]
    elif n/primNumbers[i] == 1.0:
        break 
    i+=1
print("PrimeFactors = {}".format(PrimeFactors))
print("Largest prime factor = {}".format(max(PrimeFactors)))

Output

Enter a number> 600851475143
600851475143/71 = 8462696833.0
8462696833.0/839 = 10086647.0
10086647.0/1471 = 6857.0
6857.0/6857 = 1.0
PrimeFactors = [71, 839, 1471, 6857]

Solution: Intermediate Level

At this stage we will create a program using only functions. The code from "Beginner level" will be re-used. The program will consist of three functions i.e.:

• PrimeNumbers function - function that will ask user to type in the number (n) for which we want to find the list of prime factors and the largest prime factor. The function will also create a list of prime numbers that will be used later in the code.
• FindPrimeFactorsN function - this function will create a list of prime factors that multiplied together will generate a number n that is defined by the user.
• MultiplyPrime function - this function will multiply all the prime factors obtained in with FindPrimeFacttorsN function and will show the result as output.

The entire code is given below. Output: The prime factors of 13195, and multiplication result of all prime factors in a list.

Enter a number:> 13195
13195/5 = 2639.0
2639.0/7 = 377.0
377.0/13 = 29.0
29.0/29 = 1.0
PrimeFactors = [5, 7, 13, 29]
Largest prime factor = 29
13195

Output: The prime factors of 600851475143, and multiplication result of all prime factors list.

Enter a number:> 600851475143
600851475143/71 = 8462696833.0
8462696833.0/839 = 10086647.0
10086647.0/1471 = 6857.0
6857.0/6857 = 1.0
PrimeFactors = [71, 839, 1471, 6857]
Largest prime factor = 6857
600851475143

Solution: Advanced Level

In this case the functions used from Intermediate level will be used here. The first function will be class __init__ method and the other two methods FindPrimeFactorsN, MultiplyPrime will be used without any additional modifications. The entire code i.e. class LargestPrimeNumber is given below.

class LargestPrimeNumber():
    def __init__(self):
        while True: 
            try:
                self.n = int(input("Enter a number:> "))
                break
            except ValueError:
                print("Invalid input! Please try again!")
                pass 
        self.primNumbers = [i for i in range(2, 1000+1) if 0 not in [i%self.n for n in range(2,i)]]
    def FindPrimeFactorsN(self, n, primNubmers):
        PrimeFactors = []
        i = 0 
        while i < len(self.primNumbers):
            if self.n%self.primNumbers[i] == 0:
                print("{}/{} = {}".format(self.n, self.primNumbers[i], self.n/self.primNumbers[i]))                PrimeFactors.append(self.primNumbers[i])
                self.n = self.n/self.primNumbers[i]
            elif self.n/self.primNumbers[i] == 1.0:
                break 
            i+=1
        print("PrimeFactors = {}".format(PrimeFactors))
    print("Largest prime factor = {}".format(max(PrimeFactors)))
        return PrimeFactors 
    def MultiplyPrime(self, primFactors):
        result = 1
        for x in primFactors:
            result = result*x
        print("{}".format(result))
        return result
test = LargestPrimeNumber()
primFactors = test.FindPrimeFactorsN(test.n, test.primNumbers)
res = test.MultiplyPrime(primFactors)

Output: The largest prime factor of 13195, and results of multiplication of all prime factors list

Enter a number:> 13195
13195/5 = 2639.0
2639.0/7 = 377.0
377.0/13 = 29.0
29.0/29 = 1.0
PrimeFactors = [5, 7, 13, 29]
Largest prime factor = 29
13195

Output: The largest prime factor of 600851475143, and multiplication of all prime factors list

Enter a number:> 600851475143
600851475143/71 = 8462696833.0
8462696833.0/839 = 10086647.0
10086647.0/1471 = 6857.0
6857.0/6857 = 1.0
PrimeFactors = [71, 839, 1471, 6857]
Largest prime factor = 6857
600851475143