투 포인터 .[1644]

[1. 문제 설명]

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구한다.

(N <= 4,000,000)

---

[2. 풀이 접근]

소수의 연속 합이 필요하므로, 소수 리스트를 구하도록 한다.

단순한 소수 판정법은 시간이 오래 걸린다.

 

소수를 판정 할 수 있는 여러 기법 중

에라토스테네스의 체 를 이용하여 소수 리스트를 구하도록 한다.

시간복잡도는 O(nlog(logn)) 이므로 4,000,000 이하 모든 소수를 구하는데 충분한 시간이다.

=> https://testkernelv2.tistory.com/378

 

소수 리스트를 구할 수 있으므로,

부분 합을 구하면

나머지는 여타 다른 문제들과 비슷하다.

 

head 와 tail 을 옮겨가면서 주어진 자연수가 되는지 확인하는 것이다.

---

[3. 코드]