[BOJ][실1][6588] 골드바흐의 추측

문제 링크

소수 구하기/실2

첫 번째 풀이 : 소수

알고리즘

Info Notice: 소수를 판별하는 방법1은 소수가 아닙니다. 25를 생각했을 때 2~5(제곱급)까지의 수 중에서 25를 나누어 떨어지게 하는 수가 있으면 안됩니다. 1과 자기 자신만 약수일 수 있기 때문입니다. 또는 에라토스테네스의 체를 사용합니다.

이미 소수인지 판별하면서 소수를 배열에 저장해서 사용하면 빠르게 O(N)으로 진행할 수 있습니다.

정답 코드

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

int n = 0;
const int MAX = 10010;
bool isPrime[MAX+1];

int main(void) {
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;

const int MAX = 1'000'000;

ll n, m;

bool isPrime[MAX + 1];
vector<ll> prime(MAX);
int pidx = 0;
int main()
{
    //freopen("input.txt", "r", stdin);
    //ios_base::sync_with_stdio(0); cin.tie(0);
    memset(isPrime, true, sizeof(isPrime));
    isPrime[1] = false;
    for (ll i = 2; i * i <= MAX; i++) {
        if (!isPrime[i]) continue;
        prime[pidx++] = i; // 소수를 저장
        for (ll j = i * i; j <= MAX; j += i) {
            isPrime[j] = false;
        }
    }
    while (true) {
        scanf("%d", &n);
        if (n == 0) break;
        bool flag = false;
        // prime[0] = 2이므로 제외
        for (int i = 1; i < pidx; i++) {
            if (isPrime[n - prime[i]]) {
                printf("%lld = %lld + %lld\n", n, prime[i],n - prime[i]);
                flag = true;
                break;
            }
        }
        if (!flag) {
            printf("Goldbach's conjecture is wrong.\n");
        }
    }
    return 0;
}

Success Notice: 소수 개념을 사용한 문제를 풀어봤습니다. 수고하셨습니다.