pushback

정답 코드를 바로 보기보다는 아래 글을 먼저 읽고 푸시길 바랍니다.

https://pushback.tistory.com/8

1. 기본

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int num;
    int divisor = 2;

    cin >> num;
    while (num != 1) {
        // 나누어 떨어지지 않으면
        if (num % divisor != 0) {
            divisor++;
        }
        else {
            cout << divisor << '\n';
            num /= divisor;
        }
    }
    return 0;
}

2. 개선 ver.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int num;
    int divisor = 2;

    cin >> num;
    while (num != 1) {
        if (num % divisor != 0) {
            // divisor가 짝수면 + 1, 홀수면 + 2
            divisor = divisor % 2 == 0 ? divisor + 1 : divisor + 2;
        }
        else {
            cout << divisor << '\n';
            num /= divisor;
        }
    }
    return 0;
}

3. \(\sqrt n\)까지 보기

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int main() {
    ios::ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    ll num;
    ll divisor = 2;

    cin >> num;

    for (ll div = 2LL; div * div <= num; div = div % 2 == 0 ? div + 1LL : div + 2LL) {
        while (num % div == 0) {
            cout << div << '\n';
            num /= div;
        }
    }

    if (num > 1) {
        cout << num << '\n';
    }
    return 0;
}