Project Euler 10(Python) | Summation of Primes

Question

This is my Python3 code which solved the 10th problem of Project Euler. I haven't passed the last 2 time limit test cases.

def sieve_of_eratosthenes(n):
 result = [True] * (n + 1)
 result[0] = result[1] = False
 for i in range(2, int(n**0.5)+1):
 if result[i]:
 for j in range(i*i, n+1, i):
 result[j] = False
 return [i for i in range(n+1) if result[i]]
 
t = int(input().strip())
for a0 in range(t):
 n = int(input().strip())
 result_arr = sieve_of_eratosthenes(n)
 result = sum(result_arr)
 print(result)

• user555045: What do you mean by time limit test cases? Project Euler does not have time limits, and problem 10 has only one example, not multiple test cases.
• peternish: I mean ProjectEuler+ competition held on HackerRank. Sorry for the confusion. Let's say I want a solution which can optimize my code.
• J_H: You are using a giant list. Wow, that's a lot of 64-bit pointers! Prefer to use an array of unsigned char. Then you'll use less memory, and will be more cache friendly. Fewer cache misses means greater speed.

Answer 1

It was clarified that this problem is the Hacker Rank version: https://www.hackerrank.com/contests/projecteuler/challenges/euler010/problem

This problem has the format of multiple test cases being solved in one run. The format itself suggests an approach: pre-calculate something once, then use that to solve all cases. You could first find the highest N (there is no requirement to answer the cases one by one as you read them, you can read them all first and then start answering them), or else just pre-calculate for the worst case, N only goes up to a million anyway, no big deal.

For this problem you can pre-calculate something such that you can answer each test case in constant time.

• peternish: I see your point but is there any better way to optimize the code based on this code itself?
• user555045: @peternish you could probably sieve a bit faster by using a more efficient array as J_H suggested, and you could also add up the result directly instead of making a list and then summing it. But that would have not nearly as big of an impact as only sieving once would have.