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

1. 문제

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

1644번: 소수의 연속합

 

2. 알고리즘 분류

• 수학
• 정수론
• 두 포인터
• 소수 판정
• 에라토스테네스의 체

 

3. 소스 코드

Key Point)
1. 소수를 찾는 문제는 '에라토스테네스의 체'를 활용하면 빠르게 구할 수 있다.
2. 연속 부분 수열 문제는 '두 포인터'를 활용하면 빠르게 구할 수 있다.

 

#include <iostream>
#include <vector>

using namespace std;

bool is_prime[4000006];
vector<int> prime_num;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	// 초기화
	for (int i = 0; i < 4000006; i++)
		is_prime[i] = true;

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

	// 자연수 N 입력
	cin >> N;

	// 에라토스테네스의 체를 이용한 소수 찾기
	for (int i = 2; i <= N; i++)
	{
		if (!is_prime[i]) continue; // 이미 소수 제거 당한 수는 넘어가기

		for (int j = 2; i * j <= N; j++)
			is_prime[i * j] = false;
	}
	
	// 소수들을 vector에 저장
	for (int i = 2; i <= N; i++)
		if (is_prime[i]) prime_num.push_back(i);

	// 두 포인터로 반복
	while (true)
	{
		// sum이 주어진 자연수보다 작은 경우, end index의 소수 값을 더하고 end index를 옮기기
		if (sum < N)
		{
			if (end >= prime_num.size()) break;	// 소수 인덱스를 넘어갔을 경우, break
			sum += prime_num[end];
			end++;
		}
		// sum이 주어진 자연수보다 큰 경우, start index의 소수 값을 빼고 start index를 옮기기
		else if (sum > N)
		{
			sum -= prime_num[start];
			start++;
		}
		// sum이 주어진 자연수와 같은 경우, 카운트를 올리고 end index를 옮기기
		else
		{
			ans++;
			if (end >= prime_num.size()) break; // 소수 인덱스를 넘어갔을 경우, break
			sum += prime_num[end];
			end++;
		}
	}

	// 정답 출력
	cout << ans;

	return 0;
}

 

4. 유용한 문법 및 알고리즘

 1) 에라토스테네스의 체

• 소수를 구하는 문제에서 빠르게 구할 수 있는 알고리즘

	// 에라토스테네스의 체를 이용한 소수 찾기
	for (int i = 2; i <= N; i++)
	{
		if (!is_prime[i]) continue; // 이미 소수 제거 당한 수는 넘어가기

		for (int j = 2; i * j <= N; j++)
			is_prime[i * j] = false;
	}

 

 2) 두 포인터

• 연속 부분 수열 문제를 효율적으로 해결할 수 있는 알고리즘
• start와 end 인덱스를 옮겨가면서 계산해나가는 알고리즘

	// 두 포인터로 반복
	while (true)
	{
		// sum이 주어진 자연수보다 작은 경우, end index의 소수 값을 더하고 end index를 옮기기
		if (sum < N)
		{
			if (end >= prime_num.size()) break;	// 소수 인덱스를 넘어갔을 경우, break
			sum += prime_num[end];
			end++;
		}
		// sum이 주어진 자연수보다 큰 경우, start index의 소수 값을 빼고 start index를 옮기기
		else if (sum > N)
		{
			sum -= prime_num[start];
			start++;
		}
		// sum이 주어진 자연수와 같은 경우, 카운트를 올리고 end index를 옮기기
		else
		{
			ans++;
			if (end >= prime_num.size()) break; // 소수 인덱스를 넘어갔을 경우, break
			sum += prime_num[end];
			end++;
		}
	}