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

✏️ 문제 링크

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

1644번: 소수의 연속합

 

 

✏️ 문제 설명 (더보기 클릭 👆🏻)

 

✏️ 문제 풀이

해당 문제는 에라토스테네스의 체+투포인터 알고리즘이 결합된 문제이다.

소수를 구할때 에라토스테네스의 체 방식을 사용하고, 투포인터로 연속된 소수의 합을 구한다. 

 

 

✏️ 문제 코드

#include <bits/stdc++.h>

using namespace std;
#define MAX 4000001

long a[MAX];
vector<long> prime;
void primeNum(){
    for(long i=2; i<=MAX; i++){
        a[i]=i;
    }
    for(long i=2; i<=MAX; i++){
        if(a[i]==0)continue;
        for(int j=2*i; j<=MAX; j+=i)
            a[j]=0;
    }
    
    for(long i=2; i<=MAX; i++)
        if(a[i]!=0) prime.push_back(a[i]);
    
}

int main(){
    primeNum();
    long N; cin>>N;
    
    long l=0, r=0;
    long sum=0, ans=0;
    while(l<=r && r<=prime.size()){
        if(sum<N)sum+=prime[r++];
        else if(sum>N) sum-=prime[l++];
        else{
            ans++;
            sum+=prime[r++];
        }
    }
    cout<<ans;
    
    return 0;
}

 

 

 

 ⭐ if feedback and question : comment please⭐