[백준][에라토스테네스의 체] 1644 소수의 연속 합 c++구현

목차

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

문제

 

문제 구현 방향

나는 에라토스테네스의 체를 이용하진 않고 최적화된 소수 판별 함수를 통해 해결하였다.

또한 투포인터를 이용하면 더 효율적으로 구현할 수 있었을 것 같다.

시간복잡도가 O(n)이라 어찌저찌 풀리긴 했다.

 

 

에라토스테네스의 체

외우면 도움될 것 같다. 대신 수 1000만을 넘어가면 메모리 때문에 사용이 힘들다.

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

const int max_n = 40;
bool che[max_n + 1];

// max_n까지의 소수를 생성하는 함수
vector<int> era(int mx_n) {
    vector<int> v;
    for (int i = 2; i <= mx_n; i++) {
        if (che[i]) continue;
        for (int j = 2 * i; j <= mx_n; j += i) {
            che[j] = true;
        }
    }
    for (int i = 2; i <= mx_n; i++) {
        if (!che[i]) v.push_back(i);
    }
    return v;
}

int main() {
    vector<int> a = era(max_n);
    for (int i : a) {
        cout << i << " ";
    }
    cout << endl;
    return 0;
}

 

 

코드 구현

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
#include<queue>
#include<math.h>

using namespace std;

long long int N;
vector< int> v;
int cnt = 0;

//최적화된 소수 판별 함수
bool check(int n) {
    if (n <= 1) return false;  // 1 이하의 수는 소수가 아님
    if (n == 2) return true;   // 2는 소수
    if (n % 2 == 0) return false;  // 2를 제외한 모든 짝수는 소수가 아님

    for (int i = 3; i * i <= n; i += 2) {  // 3부터 시작하여 홀수만 검사
        if (n % i == 0) return false;
    }
    
    return true;  // 위 조건들을 통과하면 소수
}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 2; i <= N; i++) {
        if (isPrime(i))
            v.push_back(i);
    }
    int idx = v.size() - 1;
    int last = v.size() - 1;
    int sum = 0;
    while (true) {
        if (v.empty())
            break;
        if (last < 0)
            break;
        if (idx >= 0) {
            sum += v[idx];
        }
        idx--;
        if (sum > N || idx < -1) {
            sum = 0;
            last--;
            idx = last;

        }
        else if (sum == N) {
            sum = 0;
            cnt++;
            last--;
            idx = last;
        }

    }
    cout << cnt;

}