Prime Factorisation

Prime Factorisation#

Prime factorisation is the process of breaking down a composite number into a product of prime numbers. The steps are as follows:

Steps:#

  1. Start with the smallest prime number: Begin with the smallest prime number, which is 2.

  2. Divide the number: Divide the number by the prime number.

  3. Check for divisibility: If the number is divisible by the prime number, record the prime factor and divide the number by this prime factor.

  4. Repeat the process: Continue the process with the resulting quotient. If the quotient is no longer divisible by the current prime, move to the next larger prime number.

  5. Continue until the quotient is 1: Repeat the steps until the quotient becomes 1. The prime factors are all the prime numbers recorded during the division process.

For a number \(n\), the prime factorisation is:

\[ n = p_1^{e_1} \times p_2^{e_2} \times \cdots \times p_k^{e_k} \]

where \(p_1, p_2, \ldots, p_k\) are prime numbers and \(e_1, e_2, \ldots, e_k\) are their respective exponents.

Functions for Finding Factors and Prime Factors#

Hide code cell source 
import sympy as sp
from sympy import *
from math import gcd
import random

def find_factors(n):
    factors = []
    for i in range(1, n + 1):
        if n % i == 0:
            factors.append(i)
    print(f"Factors of {n} are: {factors}")
    
def find_prime_factors(n):
    factors = []
    for i in range(1, n + 1):
        if n % i == 0 and sympy.isprime(i):
            factors.append(i)
    print(f"Prime factors of {n} are: {factors}")

Examples#

Example with the number \(12\)#

n = 12
find_factors(n)
find_prime_factors(n)

Factors of 12 are: [1, 2, 3, 4, 6, 12]
Prime factors of 12 are: [2, 3]

Explanation

Factors of \(12\)

For \(12\):

  • 1 divides 12: \(12 \div 1 = 12\)

  • 2 divides 12: \(12 \div 2 = 6\)

  • 3 divides 12: \(12 \div 3 = 4\)

  • 4 divides 12: \(12 \div 4 = 3\)

  • 6 divides 12: \(12 \div 6 = 2\)

  • 12 divides 12: \(12 \div 12 = 1\)

The factors of \(12\) are:

\[ [1, 2, 3, 4, 6, 12] \]

Prime Factors of \(12\)

Prime factors are the prime numbers that multiply together to give the original number. To find the prime factors of \(12\), we start with the smallest prime number and divide \(12\) by prime numbers until we cannot divide further.

  1. Divide by the smallest prime number \((2)\):

\[ 12 \div 2 = 6 \quad \text{(prime factor: 2)} \]

  1. Continue dividing by \(2\):

\[ 6 \div 2 = 3 \quad \text{(prime factor: 2)} \]

  1. \(3\) is a prime number:

\[ 3 \div 3 = 1 \quad \text{(prime factor: 3)} \]

The prime factors of \(12\) are:

\[ [2, 2, 3] \quad \text{or} \quad 2^2 \times 3 \]

Example with the number \(88\)#

n = 88
find_factors(n)
find_prime_factors(n)

Factors of 88 are: [1, 2, 4, 8, 11, 22, 44, 88]
Prime factors of 88 are: [2, 11]

Explanation

Factors of \(88\)

For \(88\):

  • 1 divides 88: \(88 \div 1 = 88\)

  • 2 divides 88: \(88 \div 2 = 44\)

  • 4 divides 88: \(88 \div 4 = 22\)

  • 8 divides 88: \(88 \div 8 = 11\)

  • 11 divides 88: \(88 \div 11 = 8\)

  • 22 divides 88: \(88 \div 22 = 4\)

  • 44 divides 88: \(88 \div 44 = 2\)

  • 88 divides 88: \(88 \div 88 = 1\)

The factors of \(88\) are:

\[ [1, 2, 4, 8, 11, 22, 44, 88] \]

Prime Factors of \(88\)

Prime factors are the prime numbers that multiply together to give the original number. To find the prime factors of \(88\), we start with the smallest prime number and divide \(88\) by prime numbers until we cannot divide further.

  1. Divide by the smallest prime number \((2)\):

\[ 88 \div 2 = 44 \quad \text{(prime factor: 2)} \]

  1. Continue dividing by \(2\):

\[ 44 \div 2 = 22 \quad \text{(prime factor: 2)} \]

  1. Continue dividing by \(2\):

\[ 22 \div 2 = 11 \quad \text{(prime factor: 2)} \]

  1. \(11\) is a prime number:

\[ 11 \div 11 = 1 \quad \text{(prime factor: 11)} \]

The prime factors of \(88\) are:

\[ [2, 2, 2, 11] \quad \text{or} \quad 2^3 \times 11 \]

Example with the number \(138\)#

n = 138
find_factors(n)
find_prime_factors(n)

Factors of 138 are: [1, 2, 3, 6, 23, 46, 69, 138]
Prime factors of 138 are: [2, 3, 23]

Explanation

Factors of \(138\)

For \(138\):

  • 1 divides 138: \(138 \div 1 = 138\)

  • 2 divides 138: \(138 \div 2 = 69\)

  • 3 divides 138: \(138 \div 3 = 46\)

  • 6 divides 138: \(138 \div 6 = 23\)

  • 23 divides 138: \(138 \div 23 = 6\)

  • 46 divides 138: \(138 \div 46 = 3\)

  • 69 divides 138: \(138 \div 69 = 2\)

  • 138 divides 138: \(138 \div 138 = 1\)

The factors of \(138\) are:

\[ [1, 2, 3, 6, 23, 46, 69, 138] \]

Prime Factors of \(138\)

Prime factors are the prime numbers that multiply together to give the original number. To find the prime factors of \(138\), we start with the smallest prime number and divide \(138\) by prime numbers until we cannot divide further.

  1. Divide by the smallest prime number \((2)\):

\[ 138 \div 2 = 69 \quad \text{(prime factor: 2)} \]

  1. Move to the next prime number \((3)\):

\[ 69 \div 3 = 23 \quad \text{(prime factor: 3)} \]

  1. \(23\) is a prime number:

\[ 23 \div 23 = 1 \quad \text{(prime factor: 23)} \]

The prime factors of \(138\) are: $\( [2, 3, 23] \)$

Example with randomly generating a number#

n = random.randint(100, 1000)
find_factors(n)
find_prime_factors(n)

Factors of 750 are: [1, 2, 3, 5, 6, 10, 15, 25, 30, 50, 75, 125, 150, 250, 375, 750]
Prime factors of 750 are: [2, 3, 5]

n = random.randint(1000, 10000)
find_factors(n)
find_prime_factors(n)

Factors of 3820 are: [1, 2, 4, 5, 10, 20, 191, 382, 764, 955, 1910, 3820]
Prime factors of 3820 are: [2, 5, 191]

n = random.randint(10000, 100000)
find_factors(n)
find_prime_factors(n)

Factors of 32130 are: [1, 2, 3, 5, 6, 7, 9, 10, 14, 15, 17, 18, 21, 27, 30, 34, 35, 42, 45, 51, 54, 63, 70, 85, 90, 102, 105, 119, 126, 135, 153, 170, 189, 210, 238, 255, 270, 306, 315, 357, 378, 459, 510, 595, 630, 714, 765, 918, 945, 1071, 1190, 1530, 1785, 1890, 2142, 2295, 3213, 3570, 4590, 5355, 6426, 10710, 16065, 32130]
Prime factors of 32130 are: [2, 3, 5, 7, 17]
Contents