문제
소수란 1보다 크고 1과 자기 자신으로만 나누어지는 정수입니다. 주어진 limit보다 엄격히 작은 모든 소수를 더하세요. limit 값 자체가 소수여도 포함하지 않습니다.
prime_sum(limit)을 구현하세요.
입력
limit: 제외 상한값입니다.
출력
조건에 맞는 소수들의 합을 반환하세요. 소수가 하나도 없으면 0을 반환합니다.
제약 조건
0 ≤ limit ≤ 2,000,000. 합은 부호 있는 64비트 정수(signed 64-bit integer)로 반환하세요.
예시
예시 1
입력:
limit = 12
예상 출력:
expected = 28입력:
long long limit = 12;
예상 출력:
long long expected = 28;입력:
long limit = 12;
예상 출력:
long expected = 28;설명
12 미만의 소수는 2, 3, 5, 7, 11이며, 이들의 합은 28입니다.
예시 2
입력:
limit = 2
예상 출력:
expected = 0입력:
long long limit = 2;
예상 출력:
long long expected = 0;입력:
long limit = 2;
예상 출력:
long expected = 0;설명
2 미만에는 소수가 없습니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
핵심은 소수를 효율적으로 찾는 것입니다. 매 수마다 나눠보는 방식은 너무 느립니다.
힌트 2
체처럼 합성수를 표시한 뒤, 표시되지 않은 수들만 더해서 limit 이하의 소수를 합산하세요.
힌트 3
limit 자체는 소수여도 제외되며, 작은 limit에서는 더할 값이 없을 수도 있습니다.
예상 복잡도
시간 O(limit log log limit), 추가 공간 O(limit)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.