So I've recently started poking at the Project Euler site, because I
feel that I need to practice writing code. For those of you interested
in solving the problems on your own I advice you to not read this, as
it will spoil the solution.
Problem 3 is this:
The prime factors of 13195 are 5, 7, 13 and 29.
What is the largest prime factor of the number 600851475143 ?
I came up with this pseudocode:
#pseudocode:
# divide by x until non-prime is found:
# if not remainder:
# check if it's prime or not:
# if not prime: exit loop
# if not prime: store in variable
# increment x by 1
Here are the functions I came up with:
def isprime(n):
if n == 1:
return False
for x in range(2, n):
if n % x == 0:
return False
else:
return True
def factorization(n):
factor = 0
x = 2
while True:
if n % x == 0:
if isprime(x):
factor = x
else:
return factor
x += 1
This, however, feels horribly inefficient. Is there a better way to do
it? I think most of my problems stem from my weak mathematical skills,
to be honest. This wasn't too bad, but even for problems 1 and 2 I've
relied on brute forcing the answer instead of looking for a
mathematical solution.
--
best regards,
Robert S.
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
http://mail.python.org/mailman/listinfo/tutor
