큰 수의 모든 약수 구하기

큰 수 N의 모든 약수를 구하는 방법.

큰 수라는 것은 int 의 범위를 넘으면서 long long 의 범위는 넘지않는 정도의 크기를 가진 수라고 생각하면 된다.

약수를 구하는 가장 쉬운 방법은 1부터 N 까지 모두 돌며 N 을 나눈 나머지가 0인 것을 모두 찾으면 된다.

하지만 N이 매우 크기 때문에 O(N) 으로는 구할 수가 없다. 그렇다면 어떻게 할까

약수들의 특성중의 하나는 서로 짝을 이룬다는 것이다. 다시말해서

N의 약수 i 가 있으면 N/i 도 약수라는 것이다. 그렇기 때문에 i가 N^0.5 를 넘어가면, 만약 약수가 존재하더라도 어차피 

앞에서 봐준 것이기 때문에 또 봐줄 필요가 없다. 즉, N^0.5 까지만 반복하면서 N 을 나눈 나머지가 0인 수 i를 찾고

i 를 찾았다면 N/i 도 같이 찾아주면 된다. 물론 i가 N의 제곱근일 경우에는 중복을 피해줘야 한다.

#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
 
using namespace std;
 
vector<long long> divisors;
long long N;
int main(){
    scanf("%lld",&N);
    for(long long i = 1; i * i <= N; i++){
        if(N % i == 0) {
            divisors.push_back(i);
            if(i != N/i) divisors.push_back(N/i);
        }
    }
    
    sort(divisors.begin(), divisors.end());
 
    for(int i = 0 ; i < divisors.size(); i++){
        printf("%lld ",divisors[i]);
    }
    return 0;
}