[백준/CPP/JS] 1644번. 소수의 연속합
[백준] 1644번. 소수의 연속합
1. 문제
하나 이상의 연속된 소수의 합으로 나타낼 수 있는 자연수들이 있다. 몇 가지 자연수의 예를 들어 보면 다음과 같다.
- 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이 연속이 아니기에 적합한 표현이 아니다. 또한 한 소수는 반드시 한 번만 덧셈에 사용될 수 있기 때문에, 3+5+5+7과 같은 표현도 적합하지 않다.
자연수가 주어졌을 때, 이 자연수를 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 구하는 프로그램을 작성하시오.
2. 입력
첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 4,000,000)
3. 출력
첫째 줄에 자연수 N을 연속된 소수의 합으로 나타낼 수 있는 경우의 수를 출력한다.
4. 풀이
- 투포인터 기본 문제인 수들의 합2와 풀이가 같다.
- 숫자 배열이 주어지지 않고 소수의 배열을 직접 구해서 사용해야 한다.
- 에라토스테네스의 체를 이용해서 소수 배열을 구해주었다.
- 그 외 풀이는 수들의 합2와 같다.
5. 코드 - cpp
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> getPrimeNums(int n)
{
vector<int> result;
vector<bool> nums(n + 2, true);
for (int i = 2; i * i <= n; i++)
if (nums[i])
for (int j = i * i; j <= n; j += i)
nums[j] = false;
for (int i = 2; i <= n; i++)
if (nums[i])
result.push_back(i);
return result;
}
int main()
{
cin.tie(NULL);
ios_base::sync_with_stdio(false);
int answer = 0;
int n;
cin >> n;
vector<int> primeNums = getPrimeNums(n);
int lt = 0;
int sum = 0;
for (int rt = 0; rt < primeNums.size(); rt++)
{
sum += primeNums[rt];
while (n < sum)
sum -= primeNums[lt++];
answer += sum == n ? 1 : 0;
}
cout << answer;
}
6. 코드 - js
function getPrimeNums(n) {
let result = [];
let nums = Array(n + 2).fill(true);
for (let i = 2; i * i <= n; i++) {
if (nums[i]) {
for (let j = i * i; j <= n; j += i) {
nums[j] = false;
}
}
}
for (let i = 2; i <= n; i++) {
if (nums[i]) result.push(i);
}
return result;
}
function solution(n) {
let answer = 0;
let pirmeNums = getPrimeNums(n);
let left = 0;
let sum = 0;
for (let right = 0; right < pirmeNums.length; right++) {
sum += pirmeNums[right];
while (n < sum) {
sum -= pirmeNums[left++];
}
answer += sum === n ? 1 : 0;
}
return answer;
}
Author And Source
이 문제에 관하여([백준/CPP/JS] 1644번. 소수의 연속합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@e7838752/boj1644저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)