I developed the following Python code to solve Project Euler problem #187, which runs correctly, but averages about 11 seconds per run. generatePrimes runs the Sieve of Eratosthenes on the odd numbers and returns all primes (does not include 2)
from utilities import generatePrimes
from time import perf_counter_ns
limit = 100000000
start = perf_counter_ns()
primes = generatePrimes(limit // 2)
answer = len(primes) + 1
for p in primes:
for q in primes:
if q > p or p * q >= limit:
break
answer += 1
end = perf_counter_ns()
print("Answer: {}".format(answer))
print("Calculated in {} seconds".format((end - start) / 1000000000))
Before I planned to optimize it, I decided to move it to a function to make the code clearer, as follows. Notice how the code is nearly identical, adjusted to be in a function.
from utilities import generatePrimes
from time import perf_counter_ns
def solve(limit: int):
primes = generatePrimes(limit // 2)
total = len(primes) + 1
for p in primes:
for q in primes:
if q > p or p * q >= limit:
break
total += 1
return total
start = perf_counter_ns()
answer = solve(100000000)
end = perf_counter_ns()
print("Answer: {}".format(answer))
print("Calculated in {} seconds".format((end - start) / 1000000000))
However, it now runs in an average of 9 seconds. Placing the initialization of start before the function definition has no noticeable effect on the time. Why does placing this code inside a function result in better performance?
