백준 1644 소수의연속합 c++ // 소수판별 알고리즘, 투포인터

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

1644번: 소수의 연속합

1. 의사코드 및 전체코드

// Authored by : BaaaaaaaaaaarkingDog
// Co-authored by : -
// http://boj.kr/ecc7d7f58ceb4679a1bb67adbb79088c
#include <bits/stdc++.h>
using namespace std;

const int MXN = 4000002;
vector<bool> seive(MXN, true);//1.모두소수라고 가정
vector<int> primes;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	for (int i = 2; i * i < MXN; ++i) {
		if (!seive[i]) continue;//소수가아니면 pass
		for (int j = i * i; j < MXN; j += i)//소수들의 배수는 소수가아님
			seive[j] = false;
	}
	for (int i = 2; i < MXN; ++i) if (seive[i]) primes.push_back(i);
	primes.push_back(0); 
	// 2 3 5 7 0 일때, 끝에 0이 있어야 7을 탐색후 e가 0을 가르킴.

	int target, s = 0, e = 1, ans = 0, tmpSum = primes[0];
	cin >> target;
	while (1) {
		if (tmpSum == target) ans++;
		if (tmpSum <= target) tmpSum += primes[e++]; //end를 한칸뒤로
		if (tmpSum > target)tmpSum -= primes[s++]; //start를 한칸뒤로
		if (e == primes.size()) break;
	}
	cout << ans;

}

 

* 25.1.30. 2회독

• 초기화 : 모두 소수라고 가정할것
• i는 i*i까지만 확인
• j는 i*i 부터 시작 // ex) 3일때, 9부터 검사하면됨
• 배수는 더하기로 구현 ( j+= i)

fill(sosu, sosu + 4000004, 1); // 모두 소수라고 가정!
sosu[0]=0; sosu[1]=0; //0, 1은 소수 아님

for(int i=2;i*i<=4000000;++i) { // i*i 까지만 검사
   if(sosu[i]) {
      // 다음배수는 더하기로 구하라.
      // 제곱부터 시작(제곱이전의 배수들은 이미 제거됨)
      for (int j = i * i; j <= 4000000; j += i) { // i의 제곱부터 배수 제거
         sosu[j] = 0;
      }
   }
}
for(int i=2;i<=4000000;++i) {
   if(sosu[i]) v.push_back(i);
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

ll n,target,ret;
int sosu[4000000+4];
vector<int> v; //소수만 담은 벡터

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

   cin>>target;

   fill(sosu, sosu + 4000004, 1); // 모두 소수라고 가정!
   sosu[0]=0; sosu[1]=0; //0, 1은 소수 아님
   
   for(int i=2;i*i<=4000000;++i) { // i*i 까지만 검사
      if(sosu[i]) {
         // 다음배수는 더하기로 구하라.
         // 제곱부터 시작(제곱이전의 배수들은 이미 제거됨)
         for (int j = i * i; j <= 4000000; j += i) { // i의 제곱부터 배수 제거
            sosu[j] = 0;
         }
      }
   }
   for(int i=2;i<=4000000;++i) {
      if(sosu[i]) v.push_back(i);
   }

   // for(int i=0;i<5;++i) {
   //    cout<<v[i]<<" ";
   // }

   int s=0, e=1; // 포함, 안포함
   int sum=v[0];
   n=v.size();
   while(e<=n) {
      if(s>=e) break;
      // cout<<"sum: "<< sum<<" ";
      if(sum < target) {
         sum+=v[e];
         e++;
      }
      else if(sum>target) {
         sum-=v[s];
         s++;
      }
      else if(sum==target) {
         ret++;
         sum-=v[s];
         s++;
      }
   }
   cout<<ret;
   
   return 0;
}

 

* 큰돌

• che에 소수가 아닌것들을 1로 기록
• 2의배수인 4부터 시작

 

* 결론

• 소수판별 알고리즘은 암기할것
• 나는 같을때 s를 뒤로해버려서 종료조건이 복잡해진듯
  • s가 e랑 같아지면 sum이 0되는 문제가 있었음
  • 이를 if(s==e) break로 해결했음
• 바킹독처럼 하는게 s,e가 자동 조절되서 (s가 e를 넘어가는 경우가 없음) 종료조건 구현하기 편한듯
  • 같을때, end를 뒤로하라!!!

이것만 고쳤더니 통과!