에라~ 소수가 뭐고, 투 포인터는 뭐냐?

문제

하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.

3 : 3 (한 가지)
41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지)
53 : 5+7+11+13+17 = 53 (두 가지)

하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.

자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)

출력

첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.

문제 아이디어

자, 이 문제를 풀기위해서는 소수를 구해야만 합니다. 제일 간단하게 소수를 구하는 방법은
```
int number = 101;
bool isPrime = false;
for (int i = 2; i < 101; i++){
  if (number % i == 0){
    isPrime = true;
    break;
  }
}
```
이렇게 하나씩 나눠보면서 나머지가 0인지 아닌지 판별해야 한다는 것을 알 수 있습니다. 그렇다면, 101이 소수인지 판별하기 위해서는 99번의 비교가 필요하고, 판별해야하는 숫자들이 많으면 시간복잡도에 턱이 떨어질 것입니다.
그렇다면 우리는 조금 더 빠른 방법으로 소수를 구해야만 합니다!! 일단 위의 코드에서 우리는 더 빠른 방법을 찾을 수 있을 것입니다. 바로 “구하려는 숫자의 제곱근까지만 판별하면 나머지는 자동으로 구해진다”는 것입니다.

예를 들면 24는 3X8, 2X12 등이 있습니다. 작은 수의 2와 3을 통해서 8과 12를 구할 수 있듯이, 작은 수만 판별해도 짝이 되는 숫자들은 알아서 구해지는 것입니다.

따라서, 우리는 위의 코드를 다음처럼 바꿀 수 있습니다.

int number = 101;
bool isPrime = false;
for (int i = 2; i < sqrt(101); i++){
  if (number % i == 0){
    isPrime = true;
    break;
  }
}

이 방법의 경우 더 빠른 속도를 가지고 있지만, 범위에서의 소수값을 판별할 때는 앞서 언급한 코드와 마찬가지로 좋은 효율을 가져다 주지 못합니다. 따라서 우리는 에라토스테네스의 체 알고리즘을 사용할 것입니다.

에라토스테네스의 체

앞서 설명한 내용들을 통해 우리는 제곱근까지만 확인해준다면 소수인지를 판별할 수 있다고 했습니다. 에라토스도 이러한 성질을 이용하고 + 더 똑똑한 생각을 했습니다.
1. 2를 소수로 판별하고, 2의 배수인 것들을 X로 체크한다.
2. 3은 체크를 당하지 않았으므로 3은 소수, 3을 체크하고 3의 배수인 것들을 X로 체크한다.
3. 4는 X로 체크 되어있으므로 PASS -> 약수가 (1,2,4)로 자신말고도 2가 포함되어있음
4. 5는 체크를 당하지 않았으므로 5는 소수, 5를 체크하고 5의 배수인 것들을 X로 체크한다.
5. …구하고자하는 범위의 제곱근까지 이 것을 반복한다면, 체크를 당하지 않은 숫자들은 소수가 될 것입니다.
  
  <출처 : 위키백과>
이 방식을 통해서는 알고리즘 문제에서 원하는 데이터 양은 충분히 제 시간 안에 돌릴 수 있을 것이다.

투 포인터

포인터라고 겁먹으면 안됩니다,,, 이 포인터는 가르킨다고 해서 포인터니깐요,,,(~~그 포인터도 주소 가르키는데~~)
2개의 포인터를 통해서 왔다리 갔다리 하면서 원하는 값을 선형시간안에 찾는 것을 말합니다. 아래 매우 간단한 예시를 들어보겠습니다.

left와 right은 처음에 인덱스 0을 가르키게 됩니다. sum 은 0으로 초기화를 시킵니다. 만약에 우리가 구하고자 하는 배열의 부분구간의 합이 10이라면, 우리는 left, right을 이동시키면서 값을 찾을 것입니다.
right이 인덱스 3까지 가는 과정은 이렇습니다.
1. sum(0)이 구하고자하는 10보다 작으므로 right이 가르키고 있는 인덱스의 값을 sum에 더해주고, right 의 인덱스를 1증가 시킵니다.
2. sum(5)가 구하고자하는 10보다 작으므로 right이 가르키고 있는 인덱스의 값을 sum에 더해주고, right의 인덱스를 1증가 시킵니다.
3. sum(8) 이 구하고자하는 10보다 작으므로, right이 가르키고 있는 인덱스의 값을 sum에 더해주고, right의 인덱스를 1증가 시킵니다.
4. sum(10)은 구하고자 하는 10이랑 같습니다. left가 가르키고 있는 값을 sum에서 빼주고 left 인덱스 값을 1 증가시킵니다.
위의 과정들을 조건에 맞게 계속 반복하다보면, right이 인덱스를 초과할 때가 있는데, 그때가 종료의 조건이 됩니다.

다양한 문제들을 투 포인터를 통해서 풀 수 있습니다. 생각하기 나름인데, 생각하기가 어렵죠,,, 다양한 문제들을 풀어보면서 익히는 수밖에 없습니다… 연습만이 살길!
이제 오늘의 문제를 넘어가도록 하죠!

문제 풀이

위에서 길게 설명했던 2가지를 이 문제에 적용해주면 됩니다.
1. 에라토스테네스의 체를 통해 소수인 리스트를 구하기
2. 리스트를 투 포인터로 이동시키며 합이 N인 구간의 갯수를 구하기
바로 코드로 넘어가도록 합시다! (위에서 설명 다 했잖아요,, 인정,,?)

백준1644 - 소수의 연속함

에라~ 소수가 뭐고, 투 포인터는 뭐냐?

문제

입력

출력

문제 아이디어

에라토스테네스의 체

투 포인터

문제 풀이

Code