[백준 1644][투포인터][C++] 소수의 연속합

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

1644번: 소수의 연속합

아리스토텔레스의 체로 소수 벡터를 구하고, 투포인터로 답을 구하는 문제였습니다.

 

문제를 처음 접하고, N의 범위가 400만까지 가는 것을 보고 아리스토텔레스의 체로 구하면 시간이 괜찮을까..? 싶어서 소수판별 관련된 이것저것 찾아봤는데,

아리스토텔레스의 체의 시간복잡도는 Nlog(logN)) 으로 생각보다 좀 많이 빨랐습니다. 머쓱

 

소수 벡터를 구한 이후로는 여타 투포인터 문제풀이를 하듯, 앞에서부터 포인터 2개로 둘 사이의 총합을 구해가며 총합이 n인 경우의 수를 구하면 됩니다.

 

#include<iostream>
#include<vector>
using namespace std;

vector<int> sosu;
bool visit[4000001]={true,true};
int n, now=2, ans, l, r;

void save_sosu(){
	for(int i=2; i<=n; i++){
		if(!visit[i]){
			sosu.push_back(i);
			for(int j=i+i; j<=n; j+=i){
				visit[j]=true;
			}
		}
	}
}

int main(){
	cin>>n;
	save_sosu();
	if(n==1){
		cout<<0<<endl;
	}
	else if(n==2){
		cout<<1<<endl;
	}
	else{
		while(sosu[l]<=n){
			if(now>=n){
				now-=sosu[l++];
			}
			else{
				if(r+1>=sosu.size()) break;
				now+=sosu[++r];
			}
			if(now==n) ans++;
		}
		cout<<ans<<endl;
	}
	
}