[C/C++] 백준 1644: 소수의 연속합 (에라토스테네스의 체 & 부분 합)

1644: 소수의 연속합

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

1644번: 소수의 연속합

 

풀이!

 이 문제를 풀기 위한 과정은 크게 2가지로 나뉜다. 첫번째로는 1부터 n번째까지의 수들 중에서 소수들을 구해야하는 것이고 두번쨰로는 부분 합을 이용하여 연속된 소수의 합으로 주어진 자연수를 나타낼 수 있는 경우의 수를 구하는 과정이다. 첫번째 과정은 소수 판정을 위한 에라토스테네스의 체를 사용하면 되고 두번째는 부분 합을 이용하면 된다.

 

 

 에라토스테네스의 체

에라토스네스의 체란?

 에라토스테네스의 체는 고대 그리스 수학자 에라토스테네스가 만들어낸 소수를 찾는 방법으로 체로 치듯이 수를 걸러낸다고 하여 뒤에 '체'가 붙게 되었다. 또한 시간복잡도가 O(n/2)인 알고리즘이기 때문에 소수를 구하는 정확한 방법이 없는 상황에서 특정한 범위까지 소수를 구하는 효과적인 방법중에 하나이다.

 

방법

    1. 소수들을 찾기 위한 과정에서 필요한 배열 find_decimal을 0으로 초기화하여 선언하고 찾은 소수들을 순서대로 저장하기 위          한 백터 index_decimal을 선언한다.

    2. 2부터 시작하여 만약 find_decimal[i]이 0이라면 소수이기 때문에 index_decimal에 저장한다.

    3. find_decimal[i]이 0인 경우 , 범위보다 작은 수까지 i의 배수들에 해당하는 값을 find_decimal에서 1로 바꾼다.

    4. 위 과정을 범위의 수까지 반복한다

 

 결국 find_decimal에서 1인 경우 이미 다른 소수의 배수이기 때문에 1인 경우에는 무시하고 지나가며 0인 경우 새로운 소수인 것을 이용한 것이다.

for(int i=2;i<=n;i++){ //소수들을 구함
    if(find_decimal[i]==0){
      int j=i;
      index_decimal.push_back(i);
      while(j<=n){
        find_decimal[j]=1;
        j+=i;
      }
    }   
  }

 

 

부분 합

 이 문제의 조건이 "연속된' 소수의 합으로 주어진 자연수를 나타낼 수 있느냐이다. 즉 연속된 합을 구하기 때문에 부분 합을 이용하면 O(n+n) 시간 안에 쉽게 값을 구할 수 있다. 부분 합에 대한 자세한 설명은 아래 포스팅을 참고하면 된다.

https://donggul-godsang.tistory.com/95

[C/C++] 백준 1806: 부분합 (누적 합 이용)

 

 다만 주의해야할 것은 last_index를 새로 넣어줘야할 때인데 i번째 index에서 부분합의 차, 즉 psum[j]-psum[i-1]이 n보다 커질 때 for문을 멈추고 현재 멈춘 j번째 index에 last_index를 넣어줘야만 다음번에 이 last_index부터 for문이 시작해 선형시간 내에 해결이 가능하다.

 

 만약 부분 합의 차이가 주어진 수와 같다면 result 변수의 값을 하나 늘려 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하면 된다.

int last_index=1;
  int result=0;
  for(int i=1;i<=m;i++){
    for(int j=last_index;j<=m;j++){
      if(psum[j]-psum[i-1]==n){
        result++; //연속된 소수합으로 표현 가능
        last_index=j;
        break;
      }
      if(psum[j]-psum[i-1]>n){
        last_index=j;
        break;
      }
    }
  }

 

 

소스코드!

#include <iostream>
#include <algorithm>
#include<bits/stdc++.h>
#include<queue>
#include<map>

using namespace std; //모든 식별자가 고유하도록 보장하는 코드 영역
int psum[4000001];
int find_decimal[4000001]; //소수들을 찾기 위한 배열
vector<int> index_decimal; //소수들의 순서를 저장

int main() {    
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n;
  cin>>n;
  
  for(int i=2;i<=n;i++){ //소수들을 구함
    if(find_decimal[i]==0){
      int j=i;
      index_decimal.push_back(i);
      while(j<=n){
        find_decimal[j]=1;
        j+=i;
      }
    }   
  }

  int m=index_decimal.size();
  for(int i=1;i<=m;i++){ //부분합을 구함
    psum[i]=psum[i-1]+index_decimal[i-1];
  }

  int last_index=1;
  int result=0;
  for(int i=1;i<=m;i++){
    for(int j=last_index;j<=m;j++){
      if(psum[j]-psum[i-1]==n){
        result++; //연속된 소수합으로 표현 가능
        last_index=j;
        break;
      }
      if(psum[j]-psum[i-1]>n){
        last_index=j;
        break;
      }
    }
  }

  cout<<result;  
}