백준 BOJ 에라토스테네스의 체, 소수 판별 문제들 풀이 220801

백준 BOJ 10482번 : Goldbach's Conjecture

문제 난이도 : Silver III

알고리즘 분류 : 에라토스테네스의 체

 

N이 주어졌을 때, N을 두 소수의 합으로 나타내는 방법의 수를 구하고 그 쌍을 모두 출력하는 문제이다.

 

에라토스테네스의 체로 N 이하의 소수들을 모두 구해놓은 뒤 1부터 N/2에 대해 모두 검사해보면 된다.

N이 32,000 이하이므로 브루트포스로 확인해도 시간 초과에 걸리지 않는다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 32001;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        vector<pair<int, int>> u;

        for(int i=1; i<=N/2; i++) {
            if(p[i] && p[N-i]) u.push_back({i, N-i});
        }

        cout << N << " has " << u.size() << " representation(s)\n";

        for(int i=0; i<u.size(); i++)
            cout << u[i].first << "+" << u[i].second << "\n";

        cout << "\n";
    }
}

 

 

백준 BOJ 13817번 : Everlasting...?

문제 난이도 : Silver II

알고리즘 분류 : 에라토스테네스의 체

 

두 수 중 어떤 수를 소인수분해 했을 때 (가장 큰 소인수) - (나머지 소인수들의 합)의 값이 더 큰 수를 구하는 문제이다.

 

빠른 소인수분해를 위해서는 에라토스테네스의 체를 활용하여 수가 1일 될 때까지 나누는 것이다.

수가 10^6보다 많이 크다면 다른 방법을 써야겠지만 일단 여기서는 10^6까지만 입력되므로, 10^6 이하의 모든 소수에 대해 나누어떨어짐을 검사해보면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e6;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    while(true) {
        int a, b; cin >> a >> b;
        if(a == 0 && b == 0) break;

        vector<int> u, w;

        for(int i=0; i<v.size() && v[i] <= a; i++) {
            if(a % v[i] == 0) u.push_back(v[i]);
        }
        for(int i=0; i<v.size() && v[i] <= b; i++) {
            if(b % v[i] == 0) w.push_back(v[i]);
        }

        int x = u[u.size() - 1];
        for(int i=0; i<u.size()-1; i++) x -= u[i];

        int y = w[w.size() - 1];
        for(int i=0; i<w.size()-1; i++) y -= w[i];

        if(x > y) cout << "a\n";
        else cout << "b\n";
    }
}

 

 

백준 BOJ 13827번 : Space Coconut Crab II

문제 난이도 : Silver II

알고리즘 분류 : 에라토스테네스의 체

 

주어진 N에 대해 삼각형의 세 변의 길이의 합이 N이고, 세 변의 길이가 모두 소수인 삼각형의 수를 구하는 문제이다.

 

에라토스테네스의 체를 이용하여 소수들을 미리 벡터에 저장해놓고, 2중 for문을 돌린 뒤 나머지 한 변의 길이를 N - v[i] - v[j]로 설정하고 이 세 변의 길이가 조건을 만족하는지 확인해보면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e6;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    while(true) {
        int N; cin >> N;
        if(N == 0) break;

        int ans = 0;

        for(int i=0; i<v.size() && v[i] < N; i++)
            for(int j=i; j<v.size() && v[i] + v[j] < N; j++) {
                int x = N - v[i] - v[j];

                if(x < v[i] || x < v[j] || x >= v[i] + v[j]) continue;

                if(upper_bound(v.begin(), v.end(), x)
                   - lower_bound(v.begin(), v.end(), x) > 0) ans++;
            }

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 15067번 : Prime Driving Conditions

문제 난이도 : Silver II

알고리즘 분류 : 에라토스테네스의 체

 

세 자리 알파벳과 네 자리 수로 이루어진 번호판이 있을 때, 네 자리 번호가 소수이면서 사전 순으로 이후에 있는 것 중 가장 빠른 번호판을 구하는 문제이다.

 

먼저 1만 이하의 모든 소수들을 에라토스테네스의 체를 이용하여 구해놓고, 네 자리 소수 중 가장 큰 소수인 9971 앞이라면 가장 빨리 나오는 소수를 구해주면 된다.

만약 그렇지 않고 다음 소수가 4자리를 넘어간다면 번호판의 알파벳이 한 칸 바뀌어야 하므로, 해당 부분을 잘 처리해주면 된다.

알파벳이 3자리까지만 있고 ZZZ는 입력되지 않는다고 하였으므로, 조건문 3개 정도를 세우면 쉽게 처리할 수 있다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e4;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    while(true) {
        string str; cin >> str;
        int N; cin >> N;

        if(str == "END" && N == 0) break;

        if(N > v.back()) {
            N = 2;

            if(str[2] != 'Z') str[2] = char(str[2] + 1);
            else if(str[1] != 'Z') str[1] = char(str[1] + 1), str[2] = 'A';
            else str[0] = char(str[0] + 1), str[1] = 'A', str[2] = 'A';
        }
        else N = v[lower_bound(v.begin(), v.end(), N) - v.begin()];

        string num = to_string(N);
        while(num.length() < 4) num = '0' + num;

        cout << str << " " << num << "\n";
    }
}

 

 

백준 BOJ 1124번 : 언더프라임

문제 난이도 : Silver II

알고리즘 분류 : 에라토스테네스의 체

 

주어진 a, b 사이의 정수들 중 소인수 분해 했을 때 소인수의 개수가 소수인 수들의 개수를 구하는 문제이다.

 

어떤 수 x에 대해 2 ~ sqrt(x) 사이의 모든 소수들에 대해서만 몇 번 나누어떨어지는지 검사하면 충분하다.

나누고 나서 1이 되면 더 이상 소인수가 없는 것이고, 1이 아니라면 그 수는 소수이다.

따라서 a ~ b의 모든 자연수에 대해서는 각각 따로 검사를 해주되, 해당 수에 대해 sqrt 시간에 탐색을 완료할 수 있도록 구현해주면 된다.

물론 소수를 미리 에라토스테네스의 체를 활용하여 저장해두고 있어야 시간 초과를 받지 않는다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e5;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int a, b; cin >> a >> b;

    int ans = 0;

    for(int i=a; i<=b; i++) {
        if(p[i]) continue;

        int temp = i, cnt = 0;

        for(int j=0; j<v.size() && v[j]*v[j] <= i; j++) {
            while(temp % v[j] == 0) {
                temp /= v[j];
                cnt++;
            }
        }
        if(temp != 1) cnt++;

        if(p[cnt]) ans++;
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 10434번 : 행복한 소수

문제 난이도 : Silver II

알고리즘 분류 : 에라토스테네스의 체

 

어떤 소수가 각 자리수를 제곱하여 더하여 새로운 수를 만드는 과정을 반복할 때 최종적으로 1에 도달하면 행복한 소수라고 할 때, 주어진 수가 행복한 소수인지를 파악하는 문제이다.

 

이 문제의 핵심은 연산을 반복하면서 1이 되는지를 파악하는 것보다도 주어진 수가 행복한 "소수"인지를 파악하는데 있다.

따라서 에라토스테네스의 체를 활용하여 미리 소수들을 구해놓고 O(1)에 소수 판별을 할 수 있도록 해준다.

그 다음에는 map이나 배열 등을 활용하여 연산을 하면서 이전에 나왔던 수가 나왔는지 정도만 체크해주면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e5;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int T; cin >> T;

    while(T--) {
        int t, N; cin >> t >> N;

        cout << t << " " << N << " ";

        if(!p[N]) {
            cout << "NO\n";
            continue;
        }

        map<int, bool> m;
        m[N] = true;

        int x = N;
        bool check = false;

        while(true) {
            int y = 0;

            while(x > 0) {
                y += (x % 10) * (x % 10);
                x /= 10;
            }

            if(y == 1) {
                check = true;
                break;
            }
            if(m[y]) break;

            m[y] = true;
            x = y;
        }

        if(check) cout << "YES\n";
        else cout << "NO\n";
    }
}

 

 

백준 BOJ 15965번 : K번째 소수

문제 난이도 : Silver II

알고리즘 분류 : 에라토스테네스의 체

 

50만 이하의 K에 대해 K번째로 작은 소수를 구하는 문제이다.

 

에라토스테네스의 체를 이용하여 벡터에 소수를 모두 구해놓고 K번째 소수를 구하면 된다.

다만 50만번째 소수가 얼마나 큰지 파악이 안되므로 범위를 직접 수정해보면서 풀이하는 것이 좋다.

코드를 돌려보면 50만번째 소수는 대략 730만 정도의 크기를 가지므로, 벡터의 크기를 1000만 이내로 잡는 것이 좋다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e7;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int N; cin >> N;

    cout << v[N-1] << "\n";
}

 

 

백준 BOJ 16424번 : Repeating Goldbachs

문제 난이도 : Silver II

알고리즘 분류 : 에라토스테네스의 체

 

어떤 수 N이 주어질 때, 두 수의 합이 N이면서 두 수의 합이 가장 큰 소수 쌍을 구하고, 두 소수의 차를 새로운 N이라고 정의하는 과정을 반복할 때 N이 3보다 작아지기 위해서 이 과정을 몇 번 거쳐야 하는지를 구하는 문제이다.

 

소수를 벡터에 미리 구해두는 과정(에라토스테네스)만 거치면 나머지는 위의 기능을 그대로 구현하기만 하면 된다.

N이 0부터 들어올 수 있으므로, 3 이하의 수에 대해 답으로 0이 나오는지 확인하고 제출하자.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e6 + 1;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int N; cin >> N;

    if(N < 4) {
        cout << 0 << "\n";
        return 0;
    }

    int ans = 0;

    while(true) {
        for(int i=0; i<v.size(); i++) {
            if(p[N - v[i]]) {
                N = (N - v[i]) - v[i];
                break;
            }
        }

        ans++;

        if(N < 3) break;
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 17014번 : Pretty Average Primes

문제 난이도 : Silver II

알고리즘 분류 : 에라토스테네스의 체

 

주어진 N에 대해 두 소수의 평균값이 N인 두 소수를 구하는 문제이다.

 

N이 100만 이하이므로, 200만까지의 소수를 에라토스테네스의 체로 구한 뒤, 소수 v[i]에 대해 2N - v[i] 또한 소수인지 체크해보면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 2e6 + 1;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        for(int i=0; i<v.size() && v[i] <= N; i++) {
            if(p[N*2 - v[i]]) {
                cout << v[i] << " " << N*2 - v[i] << "\n";
                break;
            }
        }
    }
}

 

 

백준 BOJ 21395번 : 연속한 소수 만들기

문제 난이도 : Silver II

알고리즘 분류 : 에라토스테네스의 체

 

어떤 N개의 소수를 연속한 소수로 바꿀 때, a를 b로 바꾸는 비용이 abs(a - b)라면 연속한 소수로 바꾸는 최소 비용을 구하는 문제이다.

 

이 문제에서 변수의 범위를 잘 보면 a_i 값은 10만 이하이고, N은 200 이하이므로 브루트포스로 모든 N개의 연속하는 소수에 대해 비용을 확인해볼 수 있다.

따라서 브루트포스로 모든 경우의 비용을 비교하여 그 중 최솟값을 답으로 구해주면 된다.

a_i는 10만 이하이지만 바뀐 소수는 10만보다 클 수도 있으므로 에라토스테네스의 체를 실행하는 범위를 조금 넓게 잡아주어야 한다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 150001;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        vector<int> u(N);
        for(int i=0; i<N; i++) cin >> u[i];

        sort(u.begin(), u.end());

        int ans = INT_MAX;

        for(int i=0; i<v.size()-N; i++) {
            int sum = 0;

            for(int j=0; j<N; j++) sum += abs(u[j] - v[i+j]);

            ans = min(ans, sum);
        }

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 11035번 : SÀNG

문제 난이도 : Silver III

알고리즘 분류 : 에라토스테네스의 체

 

N 이하의 수에 대해 에라토스테네스의 체 시뮬레이션을 수행할 때 M번째로 지워지는 수를 구하는 문제이다.

 

에라토스테네스의 체를 구할 때에는 2의 배수, 3의 배수, 5의 배수, ... 순으로 지워지므로 이 순서대로 수들을 bool 벡터에서 체크해보면서 M번째 체크되는 수를 구하면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M;

    while(cin >> N >> M) {
        vector<bool> v(N+1);

        int cnt = 0;
        bool check = false;

        while(true) {
            int x = 2;

            while(v[x]) x++;

            for(int i=x; i<=N; i+=x) {
                if(!v[i]) {
                    v[i] = true;
                    cnt++;

                    if(cnt == M) {
                        cout << i << "\n";

                        check = true;
                        break;
                    }
                }
            }

            if(check) break;
        }
    }
}

 

 

백준 BOJ 13469번 : Older Brother

문제 난이도 : Silver III

알고리즘 분류 : 에라토스테네스의 체

 

주어진 N이 소수의 거듭제곱인지 판별하는 문제이다.

 

먼저 N = 1인 경우 no를 출력해야 한다.

그 외에 N을 나누는 소인수가 존재하는 경우, 그 소인수로 계속 나눠 1이 되면 yes이다.

N을 나누는 소인수가 존재하는데 그 소인수로 1까지 나눠지지 않으면 no이다.

만약 sqrt(N) 이하의 모든 소수에 대해 검사했는데 나누어떨어지지 않으면 N은 소수인 것이므로 yes이다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e5;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int N; cin >> N;

    if(N == 1) {
        cout << "no\n";
        return 0;
    }

    for(int i=0; i<v.size() && v[i]*v[i] <= N; i++) {
        if(N % v[i] == 0) {
            int temp = N;

            while(temp % v[i] == 0) {
                temp /= v[i];
            }

            if(temp == 1) cout << "yes\n";
            else cout << "no\n";

            return 0;
        }
    }

    cout << "yes\n";
}

 

 

백준 BOJ 21919번 : 소수 최소 공배수

문제 난이도 : Silver III

알고리즘 분류 : 에라토스테네스의 체

 

N개의 수에 대해 소수들의 최소공배수를 구하는 문제이다.

 

먼저 각 수가 소수인지는 에라토스테네스의 체를 통해 판별이 가능하다.

서로 다른 소수는 최대공약수가 1이므로 소수일 경우 답에다 곱해주면 되는데, 문제는 같은 소수가 여러 번 입력되는 경우이다.

따라서 map을 활용하여 이전에 나온 수인 경우는 continue로 넘겨준다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e5;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int N; cin >> N;

    int ans = 1;
    bool isp = false;
    map<int, bool> m;

    while(N--) {
        int x; cin >> x;

        if(m[x]) continue;
        m[x] = true;

        bool check = true;

        for(int i=0; i<v.size() && v[i]*v[i] <= x; i++)
            if(x % v[i] == 0) check = false;

        if(check) {
            ans *= x;
            isp = true;
        }
    }

    if(isp) cout << ans << "\n";
    else cout << -1 << "\n";
}

 

 

백준 BOJ 22609번 : Matsuzaki Number

문제 난이도 : Silver III

알고리즘 분류 : 에라토스테네스의 체

 

N보다 큰 두 소수의 합을 정렬했을 때 P번째로 나오는 수를 구하는 문제이다. (이 때 두 소수가 같을 수도 있으며, 대신 a, b는 b, a와 같은 소수 배열로 본다.)

 

문제를 잘 읽어보면 P가 100 이하이다.

따라서 N보다 큰 소수 100개를 넣은 뒤, 5050개의 조합을 모두 확인함으로써 답을 찾을 수 있다.

물론 에라토스테네스의 체를 활용해서 미리 소수를 구해두어야 한다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e6;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    while(true) {
        int N, M; cin >> N >> M;
        if(N == -1 && M == -1) break;

        vector<int> u;
        int cnt = 0;

        for(int i=0; i<v.size(); i++) {
            if(v[i] > N) {
                u.push_back(v[i]);
                cnt++;

                if(cnt == 100) break;
            }
        }

        vector<int> w;

        for(int i=0; i<u.size(); i++)
            for(int j=i; j<u.size(); j++) w.push_back(u[i] + u[j]);

        sort(w.begin(), w.end());

        cout << w[M-1] << "\n";
    }
}

 

 

백준 BOJ 4134번 : 다음 소수

문제 난이도 : Silver IV

알고리즘 분류 : 소수 판정

 

정수 N이 주어질 때 N보다 크거나 같은 소수 중 가장 작은 소수를 구하는 문제이다.

 

N이 소수인지 확인하기 위해서는 sqrt(N) 이하의 소수들에 대해서만 나뉘어지는지 확인해보면 되므로, sqrt(4 x 10^9 + α) 정도의 소수들에 대해서만 확인해보면 된다.

N = 0 또는 1일 때 소수 판정이 되지 않도록 예외 처리가 필요하다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    vector<bool> p(63246, true);
    p[1] = false;

    for(int i=2; i*i<63246; i++)
        for(int j=2; i*j<63246; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<63246; i++)
        if(p[i]) v.push_back(i);

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        if(N == 0 || N == 1) {
            cout << 2 << "\n";
            continue;
        }

        for(int i=N; ; i++) {
            bool check = true;

            for(int j=0; j<v.size() && v[j]*v[j] <= i; j++) {
                if(i % v[j] == 0) {
                    check = false;
                    break;
                }
            }

            if(check) {
                cout << i << "\n";
                break;
            }
        }
    }
}

 

 

백준 BOJ 4980번 : Dirichlet's Theorem on Arithmetic Progressions

문제 난이도 : Silver IV

알고리즘 분류 : 소수 판정

 

a, b, c가 주어질 때 a + kb가 소수가 되는 c번째 소수를 구하는 문제이다. (k는 0 이상)

 

에라토스테네스의 체를 이용하여 브루트포스로 모든 a + kb에 대해 c번째 소수가 나올 때까지 반복문을 돌려주어 답을 구하는 방식을 이용하였다.

다만 N = 1일 경우 소수가 아닌데 소수라고 나올 수 있으므로 예외 처리를 적절히 해주어야 한다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    vector<bool> p(1e5, true);
    p[1] = false;

    for(int i=2; i*i<1e5; i++)
        for(int j=2; i*j<1e5; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<1e5; i++)
        if(p[i]) v.push_back(i);

    while(true) {
        int a, b, c; cin >> a >> b >> c;
        if(a == 0 && b == 0 && c == 0) break;

        int cnt = 0;

        for(int i=a; ; i+=b) {
            bool check = true;

            for(int j=0; j<v.size() && v[j]*v[j] <= i; j++) {
                if(i % v[j] == 0) {
                    check = false;
                    break;
                }
            }

            if(i == 1) check = false;

            if(check) {
                cnt++;

                if(cnt == c) {
                    cout << i << "\n";
                    break;
                }
            }
        }
    }
}

 

 

백준 BOJ 18384번 : PRIM

문제 난이도 : Silver IV

알고리즘 분류 : 소수 판정

 

5개의 수가 주어지면, 각각의 수보다 같거나 크면서 가장 작은 소수들의 합을 구하는 문제이다.

 

위의 4134번 문제에서 사용한 소스 코드를 거의 비슷하게 활용하여 구할 수 있다.

해당 코드에서 반복문을 5회 돌려서 최소 소수들을 구하고, 그 소수들을 합쳐서 답을 구해주면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    vector<bool> p(1e5, true);
    p[1] = false;

    for(int i=2; i*i<1e5; i++)
        for(int j=2; i*j<1e5; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<1e5; i++)
        if(p[i]) v.push_back(i);

    int T; cin >> T;

    while(T--) {
        int ans = 0;

        for(int k=0; k<5; k++) {
            int x; cin >> x;

            for(int i=x; ; i++) {
                bool check = true;

                for(int j=0; j<v.size() && v[j]*v[j] <= i; j++) {
                    if(i % v[j] == 0) {
                        check = false;
                        break;
                    }
                }

                if(i == 1) check = false;

                if(check) {
                    ans += i;
                    break;
                }
            }
        }

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 22302번 : Factorial Factors

문제 난이도 : Silver IV

알고리즘 분류 : 정수론

 

주어진 N에 대해, N!이 가지는 소인수의 종류의 수와 총 소인수의 개수를 구하는 문제이다.

 

먼저 N!은 최대 N 이하의 약수만을 가지고 있으므로, N까지만 확인하여 소인수의 종류를 체크해보면 된다.

총 약수의 경우는 똑같이 N 이하에 대해서 검사를 하면 되는데, 예를 들어 2의 개수를 셀 때는 ⌊ N/(2^1) ⌋ + ⌊ N/(2^2) ⌋ + ⌊ N/(2^3) ⌋ + ... 으로 구할 수 있다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    vector<bool> p(1e5, true);
    p[1] = false;

    for(int i=2; i*i<1e5; i++)
        for(int j=2; i*j<1e5; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<1e5; i++)
        if(p[i]) v.push_back(i);

    int T; cin >> T;

    while(T--) {
        int N; cin >> N;

        int a = 0, b = 0;

        vector<bool> vis(N+1);

        for(int i=0; i<v.size() && v[i] <= N; i++) a++;

        for(int i=0; i<v.size() && v[i] <= N; i++) {
            int temp = v[i];

            while(temp <= N) {
                b += N / temp;

                temp *= v[i];
            }
        }

        cout << a << " " << b << "\n";
    }
}

 

 

백준 BOJ 6052번 : Cow Pals

문제 난이도 : Silver V

알고리즘 분류 : 브루트포스

 

주어진 수 S에 대해 S 이상이면서 a의 진약수의 합이 b이고, b의 진약수의 합이 a인 두 수 a, b를 구하는 문제이다.

브루트포스로 구해주면 되지만, 완전수라는 반례가 존재한다.

완전수의 약수의 합은 자기 자신이므로 예를 들어 6을 입력할 경우 6 6이 출력으로 얻어진다.

따라서 이 두 수가 다른지도 체크를 해주어야 한다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int x; cin >> x;

    for(int i=x; ; i++) {
        int sum = 0;

        for(int j=1; j*j<=i; j++) {
            if(i % j == 0) {
                if(j * j == i) sum += j;
                else sum += j + i / j;
            }
        }

        sum -= i;

        if(i == sum) continue;

        int sum2 = 0;

        for(int j=1; j*j<=sum; j++) {
            if(sum % j == 0) {
                if(j * j == sum) sum2 += j;
                else sum2 += j + sum / j;
            }
        }

        sum2 -= sum;

        if(sum2 == i) {
            cout << i << " " << sum << "\n";
            break;
        }
    }
}

 

 

백준 BOJ 6467번 : Prime Cuts

문제 난이도 : Silver V

알고리즘 분류 : 소수 판정

 

1부터 N까지의 소수들이 있을 때, 해당 소수들 중에서 오름차순 정렬했을 때 중앙값으로부터 소수 개수가 짝수인 경우는 C*2개의 소수를, 소수 개수가 홀수인 경우는 C*2 + 1개의 소수를 출력하는 문제이다.

 

N이 1,000 이하이므로 어떠한 알고리즘으로 소수 판별을 구현하여도 문제 없다.

다만 소수의 개수의 홀짝성에 따라 경우를 잘 나눠서 소수들을 출력할 수 있도록 구현해주어야 한다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M;

    while(cin >> N >> M) {
        vector<int> v;

        for(int i=1; i<=N; i++) {
            bool check = true;

            for(int j=2; j<i; j++)
                if(i % j == 0) check = false;

            if(check) v.push_back(i);
        }

        cout << N << " " << M << ": ";

        for(int i=max((int)0, (int)((v.size() + 1)/2 - M)); i<min((int)v.size(), (int)(v.size()/2 + M)); i++)
            cout << v[i] << " ";

        cout << "\n\n";
    }
}

 

 

백준 BOJ 1747번 : 소수&팰린드롬

문제 난이도 : Silver I

알고리즘 분류 : 에라토스테네스의 체

 

N보다 크거나 같은 소수 중 가장 작은 팰린드롬 소수를 구하는 문제이다.

 

N이 100만 이하이므로 100만이 입력되었다고 해도 7자리이므로 1e7보다 작은 소수들을 에라토스테네스의 체로 구한 뒤, N 이상 가장 가까운 소수부터 검사하며 최초로 나오는 팰린드롬 수를 구하면 된다.

실제로는 100만을 입력해도 1003001이 답으로 나오기 때문에 범위를 훨씬 잡게 잡고 에라토스테네스를 돌려도 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e7;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int N; cin >> N;

    int l = lower_bound(v.begin(), v.end(), N) - v.begin();

    for(int i=l; i<v.size(); i++) {
        string str = to_string(v[i]);

        bool check = true;
        for(int j=0; j<str.length(); j++)
            if(str[j] != str[str.length()-1-j]) check = false;

        if(check) {
            cout << v[i] << "\n";
            break;
        }
    }
}

 

 

백준 BOJ 6718번 : Goldbach's conjecture

문제 난이도 : Silver I

알고리즘 분류 : 에라토스테네스의 체

 

짝수 N이 주어졌을 때, N을 두 소수의 합으로 표현할 수 있는 방법의 수를 구하는 문제이다. (이 때 두 소수는 같아도 된다.)

 

이 문제에서는 N이 2^15 이하이므로, 2^15까지의 모든 소수를 에라토스테네스의 체를 이용하여 미리 벡터에 구해놓고 모든 가능한 v[i]가 소수라면, N - v[i]가 소수인지만 체크해보면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = (1 << 15) + 1;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    while(true) {
        int N; cin >> N;
        if(N == 0) break;

        int ans = 0;

        for(int i=0; i<v.size() && v[i] <= N/2; i++)
            if(p[N - v[i]]) ans++;

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 5636번 : 소수 부분 문자열

문제 난이도 : Silver I

알고리즘 분류 : 문자열, 에라토스테네스의 체

 

255자리 이하의 수가 주어질 때, 부분 문자열이 만드는 수 중에서 10만 이하면서 가장 큰 소수를 구하는 문제이다.

 

10만 이하의 소수면 최대 5자리만 잡을 수 있기 때문에 정확하지는 않지만 대략 255 * 5개 이하의 문자열에 대해서만 검사해보면 되므로, 브루트포스 알고리즘으로 해결이 됨을 알 수 있다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e5 + 1;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    while(true) {
        string str; cin >> str;
        if(str == "0") break;

        int ans = 0;

        for(int i=0; i<str.length(); i++)
            for(int j=1; j<=5 && i-1+j<str.length(); j++) {
                int x = stoi(str.substr(i, j));
                if(p[x]) ans = max(ans, x);
            }

        cout << ans << "\n";
    }
}

 

 

백준 BOJ 1456번 : 거의 소수

문제 난이도 : Silver I

알고리즘 분류 : 에라토스테네스의 체

 

주어진 a와 b에 대해서, a 이상 b 이하이면서 소수의 2번 이상 제곱된 거듭제곱의 수를 구하는 문제이다.

 

a와 b의 최댓값이 10^14이므로 그의 제곱근인 10^7 이하의 모든 소수를 에라토스테네스의 체를 이용하여 구해준 뒤 이들을 활용하여 모든 소수들을 거듭제곱해보면서 체크하면 된다.

다만 이 문제에서 long long을 써도 overflow가 발생할 수 있는데, 나의 경우에는 오버플로우 케이스를 처리하기 귀찮으므로 그냥 치졸하게 __int128 자료형을 썼다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 1e7;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int a, b; cin >> a >> b;

    int ans = 0;

    for(int i=0; i<v.size() && v[i]*v[i] <= b; i++) {
        __int128 temp = v[i] * v[i];

        while(temp < a) temp *= v[i];

        while(temp <= b) {
            ans++;
            temp *= v[i];
        }
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 24584번 : Subprime

문제 난이도 : Silver I

알고리즘 분류 : 에라토스테네스의 체, 문자열

 

주어진 a, b와 문자열에 대해, a번째 소수 이상 b번째 소수 이하인 소수들 중 문자열을 포함하는 소수의 개수를 구하는 문제이다.

 

b의 최댓값이 10^5이므로 10^5번째 소수까지를 미리 에라토스테네스의 체 알고리즘으로 구해둔 뒤, a번째 ~ b번째 사이의 모든 소수들에 대해서 문자열을 포함하는지 직접 확인해보면 된다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int Max = 2e6;

    vector<bool> p(Max, true);
    p[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) p[i*j] = false;

    vector<int> v;
    for(int i=2; i<Max; i++)
        if(p[i]) v.push_back(i);

    int a, b; cin >> a >> b;

    string str; cin >> str;

    int ans = 0;

    for(int i=a-1; i<b; i++) {
        string num = to_string(v[i]);

        if(str.length() > num.length()) continue;

        bool check = false;

        for(int j=0; j<num.length()-str.length()+1; j++)
            if(num.substr(j, str.length()) == str) check = true;

        if(check) ans++;
    }

    cout << ans << "\n";
}