More Math Algorithms in Python Without Libraries

In today's post, we're diving into two classic number theory problems that strengthen your grasp of math logic using plain Python—no math, numpy, or sympy.

Problem 1: Get All Unique Prime Factors of an Integer

Create a Python function called get_prime_factors(n) that returns all unique prime factors of an integer n in a sorted list. Do not use built-in libraries. Assume time complexity around O(n).

Breakdown:

• If n <= 1, return an empty list (no factors).
• First, handle the even number case (2) explicitly.
• Then, check odd numbers up to the square root of n.
• Any number remaining after that loop is a prime factor.
• Use a custom sort (without sorted() or sort()) to return factors in ascending order.

Solution:

def get_prime_factors(n):
    if n <= 1:
        return []

    prime_factors = []

    if n % 2 == 0:
        prime_factors.append(2)
        while n % 2 == 0:
            n //= 2

    for i in range(3, int(n**0.5) + 1, 2):
        if n % i == 0:
            prime_factors.append(i)
            while n % i == 0:
                n //= i

    if n > 2:
        prime_factors.append(n)

    # Manual sorting (selection sort style)
    sorted_prime_factors = []
    while prime_factors:
        min_value = prime_factors[0]
        for value in prime_factors:
            if value < min_value:
                min_value = value
        sorted_prime_factors.append(min_value)
        prime_factors = [value for value in prime_factors if value != min_value]

    return sorted_prime_factors

    pass

Problem 2: Check If Two Numbers Are Co-Prime

You are given two integers a and b. Write a function are_coprime(a, b) that returns True if they are co-prime, i.e., their greatest common divisor (GCD) is 1. Do not use built-in libraries.

Breakdown:

• Use the classic Euclidean algorithm to compute the GCD manually.
• Two numbers are co-prime if gcd(a, b) == 1.
• Handle edge cases like negative or zero inputs.

Solution:

def gcd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def are_coprime(a, b):
    if a <= 0 or b <= 0:
        return False
    return gcd(a, b) == 1

    pass

These examples show how to build up number-theoretic algorithms from scratch. Practicing such problems sharpens your algorithmic reasoning and boosts your confidence for interviews and real-world coding alike!