[알고리즘] C++ 백준 1644 소수의 연속합

백준 1644

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

1644번: 소수의 연속합

풀이 전 나의 생각

자연수 N이 주어졌을 때, 이 자연수를 연속된 소수의 합으로

나타낼 수 있는 경우의 수를 구해야 한다.

 

조건

- (1 ≤ N ≤ 4,000,000)

 

과정

N은 1이상 400만 이하의 값의 범위를 가지기 때문에 데이터 타입을 int로 설정한다.

 

소수들을 더해줄 누적합의 공간은 400만을 크게 벗어나지 않을 것이기 때문에 데이터 타입을 int로 설정한다.

-> 목표로하는 소수의 합은 N이기 때문

 

소수를 구할 때 최적화 된 방법없이 2중 for문을 사용하면 400만 * 400만의 계산 횟수가 나오기 때문에

소수는 "에라토스테네스의 체" 방법을 이용하여 구한다.

 

소수의 합을 목표 자연수인 N을 구하기 위한 경우의 수를 단순 2중 for문만을 사용하면 위와 같은 계산 횟수가 나오기 때문에 투 포인터를 사용하여 구한다.

 

1. 소수의 연속된 합을 구하기 위해 소수를 미리 구해놓는다.

deci_chk[0] = deci_chk[1] = true;

	for (int i = 2; i <= sqrt(N); i++)
	{
		if (!deci_chk[i])
		{
			for (int j = i * i; j <= N; j += i)
			{
				deci_chk[j] = true;
			}
		}		
	}

에라토스테네스의 체를 이용한 방법으로

 

소수가 안된다는 의미는 1과 자신을 제외한 다른 값이 나온다는 것이다.

그럼 결국 현재 i의 값을 곱해준 값에 i를 계속 더해주면 소수가 되지 않는 값을

모두 걸러질 것이다.

 

i의 값을 곱해줘서 나온 값은 결국 어떤 값에 의해 곱해져 나온 값이니 

소수가 되지 않고 i * i를한 j 값에 i의 값만큼 계속 더해주면 와 i관련된 배수들은 모두 걸러진다.

ex) i = 2, j = 4, 6, 8, 10, 12 ... (2와 관련된 배수 모두 제외) 

 

그럼 현재 i * i를 한 배수를 구하고 있기 때문에 i는 구하고자 하는 N의 제곱근 보다 클 이유가 없다.

예를 들어 N이 400이라고 가정하면 N의 제곱근 20이 i일 때 20 * 20 이상의 수가 

이미 N의 값을 넘어 버려 구할 이유가 없기 때문이다.

 

2. 투 포인터를 사용하여 소수의 합을 구한 후, N을 기준으로 탐색 방향을 정한다.

while (start <= end)
	{
		if (sum >= N)
		{
			if (sum == N) ans++;

			sum -= decimal[start++];
		}
		else if(end == decimal.size())
		{
			break;
		}
		else
		{
			sum += decimal[end++];
		}
	}

연속된 소수의 누적합은 미리 구해놓은 소수값을 이용하여 구한다.

소수의 첫 값에 시작 포인터와 끝 포인터를 설정해주고 연속된 소수의 누적합이 

N보다 같거나 클때 까지 더해주며 끝 포인터를 증가시켜준다. 

 

N보다 같거나 크다면 더 이상 끝 포인터를 증가시킬 필요가 없기 때문에 연속된 소수의 누적합이

N보다 작아질 때 까지 시작 포인터를 증가시키며 기존에 누적되었던 소수의 값을 빼준다.

 

이 과정에서 만약 누적합과 N이 같아진다면 최종값을 증가시켜준다.

 

 

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

bool deci_chk[4000001];

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	
	int N;
	cin >> N;

	vector<int>decimal;

	deci_chk[0] = deci_chk[1] = true;

	for (int i = 2; i <= sqrt(N); i++)
	{
		if (!deci_chk[i])
		{
			for (int j = i * i; j <= N; j += i)
			{
				deci_chk[j] = true;
			}
		}		
	}

	for (int i = 0; i <= N; i++) 
	{
		if (!deci_chk[i])
		{
			decimal.push_back(i);
		}		
	}

	int start = 0, end = 0, sum = 0, ans = 0;

	while (start <= end)
	{
		if (sum >= N)
		{
			if (sum == N) ans++;

			sum -= decimal[start++];
		}
		else if(end == decimal.size())
		{
			break;
		}
		else
		{
			sum += decimal[end++];
		}
	}

	cout << ans;
}