{프로젝트 오일러/Project Euler} 10. 소수들의 합

한국어/Hackerrank - 한국어 버전과 문제가 다를 수 있습니다. 채점은 Hackerrank를 추천합니다.

1 <= 입력 개수 <= 10^4 <= 입력 값 <= 10^6

limit = 1000001 # 최댓값
primes = list(range(limit)) # 소수 리스트
primes[0] = primes[1] = 0
sum_of_primes = [0]*limit # 소수들의 합 리스트
for i in range(2, limit):
    if primes[i]:
		sum_of_primes[i] = sum_of_primes[i-1] + primes[i]
        for j in range(i*i, limit, i):
            primes[j] = 0
	else:
		sum_of_primes[i] = sum_of_primes[i-1]
for _ in range(int(input())):
    print(sum_of_primes[int(input())])

이 문제는 주어진 수와 같거나 작은 소수들의 합을 출력하는 문제입니다.

7번 문제인 10001번째 소수와 비슷한 문제입니다.

똑같이 에라토스테네스의 체 기법을 사용해 소수들을 구하며 소수들의 합도 함께 구해줍니다.

소수들의 합을 따로 구하는 이유는 그렇지 않을 경우 시간 초과가 날 수 있기 때문입니다.

소수들의 합을 구하는 과정은 어떤 소수의 값을 a, 그다음 소수의 값을 b라고 두면 a부터 b-1번째 인덱스 까지는 소수들의 합이 같습니다.

그러므로 새로운 소수를 찾으면 그 소수를 인덱스로 하고 그 전의 값(그 소수보다 작은 소수들의 합)에다가 새롭게 찾은 소수를 더한 값을 저장합니다.

(5를 찾으면 인덱스 4까지는 2와 3의 합인 5가 저장되어 있으므로 거기에 5를 더해 10을 저장하고 7을 찾으면 6까지는 10이 저장되어 있으니 10+7인 17을 저장합니다.)