약수 찾기

약수 찾기

약수를 찾는 가장 쉬운 방법은 1부터 n까지 모두 나누어보는 것이다. 하지만 n 매우 큰 수라면 시간이 오래 걸린다. 약수는 가운데 수를 중심으로 좌우의 곱이 n 이라는 점을 이용하여 O(√n) 만에 모든 약수를 구할 수 있다.

C++

vector<int> findDivisor(int n){
    vector<int> divisor;
    divisor.push_back(1);
    for(int i = 2; (i*i) <= n; i++){
        if(n%i == 0){
            divisor.push_back(i);
            divisor.push_back(n/i);
        }
    }
    divisor.push_back(n);
    return divisor;
}

반복문의 조건식은 i <= √n 의 양변에 제곱을 한 형태이다.

소수는 1보다 큰 자연수 중, 1과 자기 자신만을 약수로 가지는 수이다. 2부터 √n 사이 값 중에 단 하나라도 나누어 떨어지는 값이 있는지를 확인하여 소수 찾기에 사용할 수 도 있다.