[백준/C++] 소수의 연속합

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

이 문제를 처음 봤을 때, N까지의 소수를 구한 다음에 투 포인터로 연속합을 계산하면 되겠다고 생각했다.

 

하지만 여기서 간과한 점이 소수를 구하는데 걸리는 시간이었다.

 

처음에는 2~4,000,000까지 하나씩 전부 소수인지 검사했다.

그렇기 때문에 시간복잡도가 O(N^3/2)이 됐다. 

 

그래서 이 시간을 줄이기 위해 예전에  에라토스테네스의 체를 이용했다.

에라토스테네스의 체를 이용하면 (n/1 ~ n/n)을 전부 더한 시간복잡도로 O(NlogN)으로 소수들을 구할 수 있다.

 

그래서 에라토스테네스의 체로 소수들을 구해 빠르게 연속된 소수들의 합을 계산을 할 수 있었다.

 

현재 소수들의 합을 N과 비교할 때, 현재 소수들의 합이 N보다 크면 N보다 작을때 까지 소수들을 앞에서부터 제거한다.

만약 같거나 작다면 제거를 멈추고 다음으로 큰 소수를 더한다.

위 과정을 N까지 반복하면 된다.

 

 

​

[아이디어 정리]

1. 에라토스테네스의 체로 소수들을 빠르게 구한다.
2. 투포인터 알고리즘으로 현재 연속된 소수의 합이 N보다 크면 N보다 작거나 같아질 때 까지 소수를 제거한다.
3. 연속된 소수의 합이 N보다 같거나 작으면 다음에 올 소수를 더한다.
4. 위 과정을 N까지 반복한다.

 

 

 

Code

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <queue>
using namespace std;

int main(){
	int N;
	cin >> N;
	int nowNum = 0,retAns=0;
	vector<bool> primeCheck(N + 1, false);
	primeCheck[0] = true, primeCheck[1] = true;
	queue<int> q;
	int i = 2;
	while(i<=N)
	{
		if (!primeCheck[i])
		{
			nowNum += i;
			q.push(i);
			int j = 1;
			while(i*j<=N)
			{
				primeCheck[i * j] = true;
				j++;
			}
		}
		
		if (nowNum>N)
		{
			while(nowNum>N)
			{
				nowNum -= q.front();
				q.pop();
			}
		}

		if (nowNum == N)
		{
			nowNum -= q.front();
			q.pop();
			retAns++;
		}
		i++;
	}
	cout << retAns << endl;
	return 0;
}

 

---

처음에 루트를 Log와 헷갈려서 시간복잡도가 같다고 생각했다...

다시 생각해보니 에라토스테네스의 체는 nLog(n)의 시간복잡도에 가지치기도 가능해서 그 부분을 바꿨더니 바로 풀 수 있었다.

 

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

 

 

1644번: 연속된 소수합