Find all the prime factors of a number

Categories: Algorithms

import math

n = 13195

prime_nums = []
def is_prime(num):
    if num <= 1:
        return False
    
    if len(prime_nums) > 0:
        for ii in prime_nums:
            if num%ii == 0:
                return False
    else:
        for i in range(2, num//2):
            if num%i == 0:
                return False
    return True
   
factors = []
def get_prime_factor(num):
    if is_prime(num):
        factors.append(num)
        return 
    
    to_check = num
    for i in range(2, num):
        if is_prime(i) and to_check%i == 0:
            to_check = int(to_check/i)
            factors.append(i)
            break
            
    get_prime_factor(to_check)  

get_prime_factor(600851475143)
print(factors)

The main algorithm in the above program is the is_prime method. We should be able to check if a number is prime or not in the fastest way possible.