[SWEA] 5291 소수의 합

링크 : 5291. [파이썬 S/W 문제해결 최적화] 7일차 - 소수의 합

코드(py)

def primeNumbers():
    seive = [True] * upper  # 초기화
    seive[0] = seive[1] = False

    for i in range(2, int(upper * 0.5)):
        if seive[i]:
            for j in range(i + i, upper, i):
                seive[j] = False
                
    return seive

for tc in range(1, int(input()) + 1):
    lower, upper = map(int, input().split())
    seive = primeNumbers()
    answer = 0

    for i in range(lower + 1, len(seive)):
        if seive[i]:
            answer += i

    print(f'#{tc} {answer}')

설명

• 소수를 찾기 위해 에라토스테네스의 체를 사용.
• 에라토스테네스의 체는 2의배수, 3의배수, 4의배수 등을 각각 제거해가며 소수를 찾는 방법이다.
• seive 배열을 True값으로 초기화한다. 배열의 인덱스가 True이면 해당 인덱스 숫자가 소수임을 의미한다.
• 0, 1은 소수가 아니므로 False로 초기화한다.
• 2부터 upper의 제곱근까지에 해당하는 숫자들의 배수를 지운다. seive[i]가 True면 소수라 여기며 i씩 증가해 배수를 False로 만든다.
• seive[lower < 인덱스 < upper]에서 True인 숫자들을 합한다.