I'm working through Project Euler problems, now I'm at problem 3. I did an
implementation of the shieve of Erastothenes to find the prime numbers less
than a given number. Then I run a divisibility test over those prime
numbers to find the largest prime factor of that given number. Here's the
code:
import time
def main():
n = input("Please enter the number to find its highest prime factor: ")
start_time = time.clock()
l = p(n)
div(n,l)
print "Execution time = ",time.clock() - start_time, "seconds"
# Sieve of Eratosthenes implementation
def p(n):
is_p=[False]*2 + [True]*(n-1)
l=[]
for i in range(2, int(n**0.5)):
if is_p[i]:
for j in range(i*i, n, i):
is_p[j] = False
for i in range(2, n):
if is_p[i]:
l.append(i)
return l
def div(n,l):
for p in l :
if n%p == 0 :
h=p
print h
if __name__ == "__main__":
main()
When i test that script against 600851475143 I get the following error
How may I solve the issue?
Thanks.
_______________________________________________
Tutor maillist - Tutor@python.org
To unsubscribe or change subscription options:
https://mail.python.org/mailman/listinfo/tutor
