BOJ 1644 - 소수의 연속합

문제 링크

---

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

문제 해결

---

 1. 에라토스테네스의 체를 사용해서 소수들을 구하고 벡터에 삽입한다.

 2. 소수들의 연속된 합이 되는 개수를 구한다.

주의할 점 || 생각해볼 점

---

 1. 에라토스테네스의 체는 보통은 sqrt(N)만큼만 확인해서 소수임을 판별하는 데 사용하는 경우가 대부분인데, 이 문제에서는 sqrt(N)을 넘어가는 숫자들의 합으로 N이 될 수 있으므로, N만큼 확인해봐야한다.

 2. N의 최대 범위가 4,000,000이고 소수의 개수는 2,831,461개가 된다. for문을 이중으로 사용하나 연속된 두 소수의 합이 N이 되거나 N을 초과하게 되므로 크게 문제될 것이 없다.

  

참고

---

 - https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4 (에라토스테네스의 체)

※ 정확하고 부드러운 태클은 언제나 환영입니다.