이백만 이하 소수의 합

사이트 이름 - 문제 10번

• 이백만 이하 소수의 합

10 이하의 소수를 모두 더하면 2 + 3 + 5 + 7 = 17 이 됩니다.

이백만(2,000,000) 이하 소수의 합은 얼마입니까?

해결 방법

이것도 기존에 사용했던 소수 구하는 알고리즘을 이용하면 되겠다.

def is_prime(number):
    if number < 2:
        return False

    if number == 2:
        return True
    
    if number % 2 == 0:
        return False

    for i in range(3, int(number ** 0.5) + 1):
        if number % i == 0:
            return False

    return True


sum = 2
for i in range(3, 2000001):
    if is_prime(i):
        sum += i

print(sum)

해설

이번 문제는 에라토스테네스의 체를 이용해 구하는것이라고 한다.

다음에 시간을 내서 에라토스테네스의 체를 한 번 구현해 봐야겠다.