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)
  • \$\begingroup\$ 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. \$\endgroup\$
    – harold
    Nov 14 at 11:35
  • \$\begingroup\$ I mean ProjectEuler+ competition held on HackerRank. Sorry for the confusion. Let's say I want a solution which can optimize my code. \$\endgroup\$
    – peternish
    Nov 14 at 12:34
  • \$\begingroup\$ 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. \$\endgroup\$
    – J_H
    Nov 14 at 17:05

1 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.

  • \$\begingroup\$ I see your point but is there any better way to optimize the code based on this code itself? \$\endgroup\$
    – peternish
    Nov 15 at 1:00
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – harold
    Nov 15 at 9:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.