[BOJ/C, C++] 단계별로 풀어보기 - 약수, 배수와 소수 1

#programming #c #cpp #coding

2026.01.03일자 입니다. 약수, 배수와 소수 1 풀어보았습니다.
문제가 많지 않기도 하고 쉽기도 해서 얼마 안 걸렸습니다.

2501번 약수 구하기

#include <stdio.h>
int main() {
    int N, K, cnt = 0; scanf("%d %d", &N, &K);
    for (int i = 1; i <= N; ++i) {
        if (N % i == 0) { if (++cnt == K) { printf("%d", i); return 0; } }
    } printf("0");
}

1부터 N까지 약수를 찾으며 카운팅합니다. K번째라면 해당 수를 출력 후 프로그램을 종료합니다.
반복문이 성공적으로 종료되었다는 뜻은 K번째 약수가 존재하지 않아 반복문이 조기종료 되지 않았다는 뜻이므로 0을 출력합니다.

문제와는 관련 없지만 제가 1년 전에 c++로 작성한 코드에는 return 0; 대신에 exit(0);이 작성되어 있어 두 코드의 차이를 알아보았습니다.
두 함수 모두 프로그램이 성공적으로 종료되었음을 운영체제에 알리는 함수입니다.
return 0;은 함수를 종료하며 지역 변수들의 소멸자를 정상적으로 호출합니다. 하지만 프로그램 종료는 오직 main 함수 내에 작성하여야만 가능합니다.
exit(0)은 <cstdlib> 내에 포함되어 프로그램을 즉시 종료합니다. 따라서 지역 변수의 소멸자를 호출하지 않고 즉시 종료하지만 어느 함수에서든 즉시 종료가 가능합니다.
보통 코테에서는 return 0; 방식을 쓰는 게 일반적인 것으로 알고 있는데 1년 전의 저는 무슨 생각으로 exit(0)을 쓴 건지 잘 모르겠습니다.

9506번 약수들의 합

문제 링크

#include <iostream>
#include <vector>
using namespace std;
int main() {
    while (true) {
        int n; cin >> n; if (n == -1) break;
        vector<int> arr; int sum = 0;
        for (int i = 1; i < n; ++i) { if (n % i == 0) { arr.push_back(i); sum += i; } }
        cout << n; if (sum == n) {
            cout << " = ";
            for (int i = 0; i < arr.size() - 1; ++i) cout << arr[i] << " + ";
            cout << arr[arr.size() - 1] << '\n';
        } else cout << " is NOT perfect.\n";
    }
}

자기 자신을 제외한 약수들과 합을 구한 뒤 약수들의 합이 그 수와 같은지 판단하여 조건에 따라 출력합니다.
일반 배열을 이용하여 풀 수도 있었으나 인덱스 변수를 따로 선언하여야 하기 때문에 push_back이 가능한 vector 컨테이너를 사용하였습니다.

1978번 소수 찾기

문제 링크

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int N; cin >> N; int cnt = N;
    while (N--) {
        int T; cin >> T;
        if (T == 1) --cnt;
        for (int i = 2; i <= sqrt(T); ++i) {
            if (T % i == 0) { --cnt; break; }
        }
    } cout << cnt;
}

1은 소수가 아니기에 미리 배제하였고 2부터 해당수를 나누어가며 소수인지 판단하였습니다.
여기서 소수 판단 루프의 조건을 i <= sqrt(T)라고 작성하였는데 이는 약수의 대칭성을 이용한 조건입니다.

n의 약수 a를 찾으면 n/a 라는 약수까지 찾을 수 있습니다. 이것이 약수의 대칭성이며 대칭의 기준은 n의 제곱근입니다.
따라서 2부터 n까지 검사할 필요 없이 n의 제곱근까지만 확인하면 됩니다.

그리고 생각해보니까 i <= sqrt(T)랑 i*i <= T랑 같은 식이라 cmath, sqrt 안 써도 되더라고요.
당시에는 생각이 안 났습니다.

2581번 소수

문제 링크
블로그를 쓰면서 다시 보니 약수들의 합과 매우 비슷한 문제라는 생각이 듭니다. 약수에서 소수로 바뀐 것 같습니다.

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int M, N; cin >> M >> N;
    int min_val = 0, total = 0;
    for (int i = M; i <= N; ++i) {
        if (i == 1) continue;
        int j = 2, len = sqrt(i);
        for (; j <= len; ++j) { if (i % j == 0) break; }
        if (j > len) { if (!min_val) min_val = i; total += i; }
    } total == 0 ? cout << -1 : cout << total << '\n' << min_val;
}

M ~ N에서 소수를 찾습니다. 1은 소수가 아니므로 먼저 배제합니다.
이후 2부터 해당 수의 제곱근까지 나누어가며 나누어 떨어진다면 소수가 아니므로 검사를 종료합니다.
반복문이 성공적으로 종료되었다면 나누어 떨어지는 수가 없는 것이므로 소수라고 판단할 수 있습니다.

11653번 소인수분해

문제 링크

#include <iostream>
using namespace std;
int main() {
    int N; cin >> N; if (N == 1) return 0;
    for (int i = 2; i <= N; ++i) { while (N % i == 0) { cout << i << '\n'; N /= i; } }
}