TheAlgorithms-Python
61 строка · 1.6 Кб
1"""
2Project Euler Problem 10: https://projecteuler.net/problem=10
3
4Summation of primes
5
6The sum of the primes below 10 is 2 + 3 + 5 + 7 = 17.
7
8Find the sum of all the primes below two million.
9
10References:
11- https://en.wikipedia.org/wiki/Prime_number
12- https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
13"""
14
15
16def solution(n: int = 2000000) -> int:17"""18Returns the sum of all the primes below n using Sieve of Eratosthenes:
19
20The sieve of Eratosthenes is one of the most efficient ways to find all primes
21smaller than n when n is smaller than 10 million. Only for positive numbers.
22
23>>> solution(1000)
2476127
25>>> solution(5000)
261548136
27>>> solution(10000)
285736396
29>>> solution(7)
3010
31>>> solution(7.1) # doctest: +ELLIPSIS
32Traceback (most recent call last):
33...
34TypeError: 'float' object cannot be interpreted as an integer
35>>> solution(-7) # doctest: +ELLIPSIS
36Traceback (most recent call last):
37...
38IndexError: list assignment index out of range
39>>> solution("seven") # doctest: +ELLIPSIS
40Traceback (most recent call last):
41...
42TypeError: can only concatenate str (not "int") to str
43"""
44
45primality_list = [0 for i in range(n + 1)]46primality_list[0] = 147primality_list[1] = 148
49for i in range(2, int(n**0.5) + 1):50if primality_list[i] == 0:51for j in range(i * i, n + 1, i):52primality_list[j] = 153sum_of_primes = 054for i in range(n):55if primality_list[i] == 0:56sum_of_primes += i57return sum_of_primes58
59
60if __name__ == "__main__":61print(f"{solution() = }")62