I solved Problem 10 of Project Euler with the following code, which works through brute force:
def isPrime(n):
for x in range(2, int(n**0.5)+1):
if n % x == 0:
return False
return True
def primeList(n):
primes = []
for i in range(2,n):
if isPrime(i):
primes.append(i)
return primes
def sumPrimes(primelist):
prime_sum = sum(primelist)
return prime_sum
print (sumPrimes(primeList(2000000)))
The three functions work as follows:
isPrime checks whether a number is a prime;
primeList returns a list containing a set of prime numbers for a certain range with limit 'n', and;
sumPrimes sums up the values of all numbers in a list. (This last function isn't needed, but I liked the clarity of it, especially for a beginner like me.)
I then wrote a new function, primeListRec, which does exactly the same thing as primeList, to help me better understand recursion:
def primeListRec(i, n):
primes = []
#print i
if (i != n):
primes.extend(primeListRec(i+1,n))
if (isPrime(i)):
primes.append(i)
return primes
return primes
The above recursive function worked, but only for very small values, like '500'. The function caused my program to crash when I put in '1000'. And when I put in a value like '2000', Python gave me this:
RuntimeError: maximum recursion depth exceeded.
What did I do wrong with my recursive function? Or is there some specific way to avoid a recursion limit?
