[Python] 백준 1644번 : 소수의 연속합

https://www.acmicpc.net/problem/1644

1644번: 소수의 연속합

---

💡 문제 풀이

투 포인터 문제이다.

 

소수랑 섞은 문제인데 범위가 4백만까지 이므로 에라토스테네스의 체를 사용해서 소수를 찾아준다.

찾은 소수를 대상으로 투 포인터 알고리즘 중 특정 값과 일치하는 부분 배열을 찾는 알고리즘으로 카운트하면 된다.

✔️ 느낀 점

그렇게 어렵지 않았는데 시간이 생각보다 오래 걸리는 풀이여서 더 나은 코드로 바꾸고 싶었으나 굳이 그러기엔 너무 귀찮아서 넘어가야겠다.

💻 코드

N = int(input())

prime_nums = [True] * (N+1)
for i in range(2, int(N**0.5)+1):
    if prime_nums[i]:
        for j in range(i+i, (N+1), i):
            prime_nums[j] = False
  
end, sum_, cnt = 2, 0, 0

for start in range(2, N+1):
    if not prime_nums[start]: continue
    while sum_ < N and end < N+1:
        if not prime_nums[end]: 
            end += 1
            continue
        sum_ += end
        end += 1
    if sum_ == N: cnt += 1
    sum_ -= start
    
print(cnt)