문제 해결 아이디어)
입력값까지의 소수들을 리스트에 담고,
투포인터로 리스트의 연속된 소수들이 입력값을 만드는지 확인한다.
[1] 특정 범위의 소수들 구하기
is_prime = [False, False] + [True]*(n-1) # 0,1 빼고 모두 소수라 가정
for i in range(2, int(math.sqrt(n))+1): #판별 대상의 수
if is_prime[i]: #소수판별
for j in range(i*i, n+1, i):
is_prime[j] = False #소수의 배수는 소수가 아니다. 이 때, 소수의 제곱 수부터 확인해보면 된다.
for k in range(len(is_prime)):
if is_prime[k]:
nums.append(k)에라토스테네스의 체
-
리스트 생성: 우리는 소수인지 여부를 저장할 리스트를 만듭니다. 이 리스트의 인덱스는 숫자를 나타내며, 각 인덱스에 해당하는 값은 그 숫자가 소수인지를 나타냅니다.
- 처음에는 0과 1을 소수가 아니므로 False로 설정하고, 나머지는 모두 소수라고 가정하여 True로 설정합니다.
-
반복문 실행:
- 2부터 시작해서 해당 숫자가 소수라고 표시되어 있으면, 그 숫자의 배수들을 모두 제거(즉, False로 표시)합니다. 배수를 제거하는 이유는, 소수의 배수들은 더 이상 소수가 될 수 없기 때문입니다.
- 이 과정을 숫자의 제곱근까지 반복합니다. 그 이유는 배수를 처리할 때, 제곱근 이상의 배수는 이미 앞에서 처리되었기 때문입니다.
-
남은 수들 선택: 배수 제거가 끝난 후 True로 남아있는 수들은 모두 소수입니다.
왜 number * number부터 시작하나요?
이것은 에라토스테네스의 체가 효율적인 이유 중 하나입니다. 예를 들어, 이미 작은 소수들의 배수는 이전에 처리되었으므로 중복 작업을 피하려는 것입니다. 자세한 이유는 다음과 같습니다:
number가 3일 때, 2 * 3 = 6은 이미 2의 배수로 처리되었습니다.
따라서, number가 3일 때는 3의 제곱인 9부터 배수 처리를 시작하면 됩니다.
이런 방식으로 이미 처리된 배수들을 다시 확인하지 않아도 되므로 효율적입니다.
세부 설명
range(number * number, limit + 1, number):
number * number: number의 배수는 2부터 시작하지 않고, 최소 number * number부터 시작합니다. 그 이유는 그 이전의 배수들은 이미 다른 소수들에 의해 처리되었기 때문입니다.
예를 들어, number가 3이라면, 3의 배수는 6, 9, 12, ...입니다. 하지만 6은 이미 2의 배수에서 처리되었기 때문에, 3의 배수는 9부터 확인하면 됩니다.
limit + 1: range 함수의 끝 경계는 포함되지 않기 때문에, limit까지 포함하기 위해 limit + 1로 설정합니다.
number: number의 배수를 찾기 위해 한 번에 number씩 더해가며 범위를 설정합니다. 즉, number, 2 number, 3 number...의 순서대로 배수를 처리합니다.
[2] 투포인터
소수의 리스트에서 start와 end 포인터 두개로 잡고 둘 다 인덱스 0에서 시작한다.
end를 증가시키며 누적합을 구할 건데, 주어진 수 n보다 크면 start를 증가시켜 여기에 해당하는 값을 빼주며 총합을 줄여 조절한다.
import sys
import math
input = sys.stdin.readline
n = int(input())
nums = []
is_prime = [False, False] + [True]*(n-1) # 0,1 빼고 모두 소수라 가정
for i in range(2, int(math.sqrt(n))+1): #판별 대상의 수
if is_prime[i]: #소수판별
for j in range(i*i, n+1, i):
is_prime[j] = False #소수의 배수는 소수가 아니다. 이 때, 소수의 제곱 수부터 확인해보면 된다.
for k in range(len(is_prime)):
if is_prime[k]:
nums.append(k)
s, e = 0, 0
sumi = 0
result = 0
while True:
while sumi > n and s <= e:
sumi -= nums[s]
s += 1
if sumi == n:
result += 1
if e >= len(nums):
break
sumi += nums[e]
e += 1
print(result)
