Skip to content

Instantly share code, notes, and snippets.

@ebartrum
Created November 30, 2014 21:59
Show Gist options
  • Save ebartrum/476502dac9171dfc15a0 to your computer and use it in GitHub Desktop.
Save ebartrum/476502dac9171dfc15a0 to your computer and use it in GitHub Desktop.
A solution to the 3rd Euler Challenge
"""The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?"""
#I want to define prime(x) which gives x's prime factors
#Define factor(x)
def factor(x):
array=[]
i=1
while (i<=x):
if x%i==0:
array.append(i)
i+=1
return array
#Define prime test
def prime(x):
if factor(x)==[1,x]:
return True
else:
return False
# Define a function nextPrime(x) that returns the least prime greater than x
def nextPrime(x):
y=x+1
while prime(y)==False:
y+=1
return y
# Define a function giving the prime factorisation of x
def primeFactorisation(x):
array=[]
y=x
while y>1:
z=2
while y%z!=0:
z=nextPrime(z)
array.append(z)
y=y/z
return array
z=primeFactorisation(600851475143)
print(max(z))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment