Skip to content

Instantly share code, notes, and snippets.

@ssshukla26
Last active November 24, 2021 06:47
Show Gist options
  • Save ssshukla26/04f5541157c0ba8dfe1cd9a4737499f1 to your computer and use it in GitHub Desktop.
Save ssshukla26/04f5541157c0ba8dfe1cd9a4737499f1 to your computer and use it in GitHub Desktop.
Get all prime factors of a number
# Function to find prime factors of a number
def primeFactors(num):
# Function to reduce num by a factor
def reduceByFactor(factor):
nonlocal num
while num % factor == 0:
num = num // factor
return
# Init
primes = set()
# Reduce by factor of 2
div = 2
if num % div == 0:
primes.add(div)
reduceByFactor(div)
# Reduce by all other prime nums
div = 3
while div <= num:
if num % div == 0:
primes.add(div)
reduceByFactor(div)
div += 2
return primes
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment