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!