자연수 을 나누어떨어지게 하는 자연수가 의 약수입니다. 가 약수이면 도 약수이며 두 수의 곱은 입니다.
두 약수가 모두 보다 크면 곱이 보다 커집니다. 따라서 부터 까지 검사하면 모든 약수 쌍을 찾을 수 있습니다.
의 약수 쌍은 입니다. 의 처럼 두 값이 같으면 한 번만 기록합니다. 오름차순 출력이 필요하면 모은 약수를 정렬합니다.
예를 들어 에서 을 검사하면 반대쪽 약수 도 함께 얻습니다. 를 다시 검사하면 이미 얻은 쌍을 반대로 확인하게 됩니다. 작은 쪽만 검사해도 모든 약수를 얻는 이유입니다. 약수 목록을 직접 나열해야 하는 문제에 이 방법을 사용합니다.
자연수를 , 약수 개수를 라고 합니다.
| 연산 | 시간복잡도 | 공간복잡도 |
|---|---|---|
| 약수 탐색·정렬 | 결과 저장 |
양의 정수의 모든 약수를 오름차순으로 출력하여라.
첫째 줄에 양의 정수 이 주어진다. 이다.
약수를 한 줄에 공백으로 구분하여 출력한다.
12
1 2 3 4 6 12
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
vector<int> v;
int main() {
int n, i;
cin >> n;
for (i = 1; i <= n / i; ++i) {
if (n % i == 0) {
v.push_back(i);
if (i != n / i) v.push_back(n / i);
}
}
sort(v.begin(), v.end());
for (int x : v) {
cout << x << ' ';
}
cout << '\n';
}import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner in;
int n, i;
ArrayList<Integer> lst;
in = new Scanner(System.in);
n = in.nextInt();
lst = new ArrayList<>();
for (i = 1; i <= n / i; ++i) {
if (n % i == 0) {
lst.add(i);
if (i != n / i) lst.add(n / i);
}
}
Collections.sort(lst);
for (int x : lst) {
System.out.print(x + " ");
}
System.out.println();
}
}n = int(input())
lst = []
i = 1
while i * i <= n:
if n % i == 0:
lst.append(i)
if i != n // i:
lst.append(n // i)
i += 1
print(*sorted(lst))