https://www.acmicpc.net/problem/1644
1644번: 소수의 연속합
문제 하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다. 3 : 3 (한 가지) 41 : 2+3+5+7+11+13 = 11+13+17 = 41 (세 가지) 53 : 5+7+11+13+17 = 53 (두 가지) 하지만 연속된 소수의 합으로 나타낼 수 없는 자연수들도 있는데, 20이 그 예이다. 7+13을 계산하면 20이 되기는 하나 7과 13이 연속이 아니기에 적합한 표현이 아니다. 또한 한
www.acmicpc.net
에라토스테네스의 체와 구간 합 알고리즘을 합친 문제다. n이하의 소수를 모두 구하여 연속된 소수의 합이 n이 되는 순간 경우의 수를 증가시키면 된다. 구간합 알고리즘은 셩님블로그를 참고하였다.
ex1.)입력이 24인 경우
2 3 5 7 11 13 17 19 23 : 24이하 소수의 갯수는 9, 따라서 r은 9이면 탈출
24이면
2 -> 2
2 3 -> 5
2 3 5 -> 10
2 3 5 7 -> 17
2 3 5 7 11 -> 28
3 5 7 11 -> 26
5 7 11 -> 23
5 7 11 13 -> 36
7 11 13 -> 31
11 13 -> 24
13 -> 13
13 17 -> 30
17 -> 17
17 19 -> 36
19 -> 19
19 23 -> 42
23 -> 23, r = 9라서 마지막이라 탈출
#include <iostream>
#include <vector>
#include <string.h>
using namespace std;
int mat[4000001];
int n;
int cnt = 0, sum = 0, l = 0, r = 0;
vector<int> v;
//소수 찾기 알고리즘, n이하인 모든 소수를 찾는다.
void Prime() {
//모든 수를 자기자신으로 초기화
for (int i = 1; i <= n; i++) {
mat[i] = i;
}
for (int i = 2; i <= n; i++) {
if (!mat[i]) { //소수가 아니면
continue; //건너뛴다.
}
for (int j = i + i; j <= n; j += i) { //현재 i에 2 * i를 한 수부터 소수를 찾는다.
mat[j] = 0; //소수가 아니니까 0으로 만든다.
}
}
//소수가 아니면 벡터에 삽입
for (int i = 2; i <= n; i++) {
if (mat[i]) {
v.push_back(mat[i]);
}
}
}
int main() {
cin >> n;
Prime(); //소수 찾기 알고리즘
//구간 합 알고리즘, 연속된 수의 특정 구간 합을 구할 때 사용
//l과 r사이의 구간합 구하기
//구간 합이 n보다 크면 현재 l위치에 있는 수를 뺀다.
//구간 합이 n보다 작으면 현재 r위치에 있는 수를 더한다.
while (1) {
if (sum >= n) {
sum = sum - v[l];
l++;
}
else if (r == v.size()) {
break;
}
else {
sum = sum + v[r];
r++;
}
if (sum == n) {
cnt++;
}
}
cout << cnt;
}
'백준' 카테고리의 다른 글
백준2503 - 숫자 야구 (0) | 2019.08.01 |
---|---|
백준1236 - 성 지키기 (0) | 2019.07.31 |
백준5566 - 주사위 게임 (0) | 2019.07.31 |
백준17214 - 다항 함수의 적분 (0) | 2019.07.30 |
백준4889 - 안정적인 문자열 (0) | 2019.07.30 |