Skip to content

Instantly share code, notes, and snippets.

@captflint
Created November 3, 2014 04:18
Show Gist options
  • Save captflint/be54091d56c14dc61b24 to your computer and use it in GitHub Desktop.
Save captflint/be54091d56c14dc61b24 to your computer and use it in GitHub Desktop.
Prime factor finder
# This program takes an integer and returns it prime factors
# isprime checks whether an integer greater than 2 is prime
def isprime(candn):
half = candn / 2
divisor = 2
while divisor <= half:
if candn % divisor == 0:
return(False)
else:
divisor += 1
return(True)
# nextprime is meant to replace genplist
def nextprime(lastprime):
nprime = lastprime + 2
while True:
if isprime(nprime):
return(nprime)
else:
nprime += 2
def pffind(num):
if isprime(num):
return([num])
else:
plist = [2, 3]
flist = []
partial = num
while isprime(partial) is False:
primefactor = 0
for prime in plist:
if (partial % prime) == 0:
primefactor = prime
break
if primefactor == 0:
plist.append(nextprime(plist[-1]))
else:
flist.append(primefactor)
partial = partial / primefactor
flist.append(int(partial))
return(flist)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment