In this tutorial, you will learn to write a Python program to find the Prime factors of a given input integer. Prime factorization is a mathematical process of breaking down a number into its prime factors.
We can also say that it is a representation of a composite number as a product of its prime factors. In this post, we will see the various logic to write a Python program to find prime factors of a given integer.
To find the prime factors of a given integer we have to factorize it. Factorization means finding the prime numbers that divide the given integer. We can use different methods to factorize the integer. One of the methods is trial division. is trial division this method, we divide the number by the smallest prime factor, then divide the quotient by the next smallest prime factor, and continue the process until we reach a quotient of 1.
What is Prime Factor?
Prime factors of a number are the prime numbers that divide that number exactly, without leaving a remainder. In mathematical terms, if you have a number n, its prime factors are the set of prime numbers that can be multiplied together to equal n.
Key Concepts about Prime Factors:
- Prime Number: A prime number is a natural number greater than 1 that has no positive divisors other than 1 and itself. For example, the numbers 2, 3, 5, and 7 are prime numbers because they can only be divided evenly by 1 and themselves.
- Factorization: This is the process of breaking down a number into its constituent factors. For prime factorization, these factors are all prime numbers.
Example of Prime Factorization:
Let’s consider the number 60:
- Start dividing 60 by the smallest prime number, which is 2.
- 60÷2=30
- Continue dividing by 2 until you cannot divide evenly by 2 anymore.
- 30÷2=15
- Move to the next smallest prime number, which is 3.
- 15÷3=5
- The result 5 is itself a prime number, so we stop here.
The prime factors of 60 are therefore 2,2,3, and 5. This can be expressed as 2^2×3×5.
Properties of Prime Factors:
- Unique Factorization: Every integer greater than 1 either is a prime number itself or can be uniquely factored into prime numbers, up to the order of the factors. This is known as the Fundamental Theorem of Arithmetic.
- Use in GCD and LCM: The greatest common divisor (GCD) and the least common multiple (LCM) of two numbers can be determined from their prime factorizations.
- Applications: Prime factorization is critical in various fields, particularly in cryptography, where large prime numbers are used to encrypt information securely.
Find Prime factors of given Integer in Python
Program 1: Using Trial Division
In this method, we will use trial division to find the prime factors of a given integer. We will start with the smallest prime factor and divide the integer until the quotient becomes 1. If the quotient is divisible by a prime factor, we will add that factor to the list of prime factors.
def prime_factors(n):
i = 2
factors = []
while i * i <= n:
if n % i:
i += 1
else:
n //= i
factors.append(i)
if n > 1:
factors.append(n)
return factors
num = int(input("Please enter a number: "))
print("Prime factors of", num, "are:", prime_factors(num))Output :
Enter a number: 24 Prime factors of 24 are: [2, 2, 2, 3]
Program 2: Optimized Trial Division Using 2 and Odd Numbers
This approach improves upon the basic trial division by initially dividing out all factors of 2 (the only even prime number), and then using a loop that increments by 2 to check only odd numbers.
num = int(input("Please enter a number: "))
n = num
factors = []
while n % 2 == 0:
factors.append(2)
n //= 2
factor = 3
while factor * factor <= n:
while n % factor == 0:
factors.append(factor)
n //= factor
factor += 2
if n > 1:
factors.append(n)
print("Prime factors of", num, "are:", factors)Output:
Please enter a number: 9 Prime factors of 9 are: [3, 3]
Explanation:
This method is more efficient than checking every single number up to n because it reduces the number of division operations by half after dealing with the factor of 2.