C++ 약수 개수를 구하는 로직

 

약수 란?

두 정수 a, b에 대하여 b=ac를 만족하는 정수 c가 존재한다면, a를 b의 약수라고 한다.

 

 

주어진 1이상의 자연수 n 에 대해서,

약수의 개수가 몇개인지 구하는 로직

// 주어진 n (1 이상인 자연수)의 약수개수를 구한다.
int get_count_divisor( int n )
{
    // n 이 1인 경우, 약수는 1개
    if( n == 1 )
    	return 1;


    // 약수 개수 담을 변수
    // 1보다 큰 자연수 n의 약수에 '1'과 'n' 은 항상 포함되기 때문에
    // 최소 약소개수를 2로 초기화함
    int divisorCount = 2;

    // 약수인지 체크하는 범위는
    // 2부터 n의 절반까지만 잡으면 됨 
    for( int i=2 ; i <= n/2 ; i++ ) {
    	if( n % i == 0 ){
        	divisionCount++;
     	}
    }
    
    return divisorCount;
}

 

 

- 1의 약수는 1 본인 1개만 존재한다.

 

- 2부터 약수는 1과 본인, 최소 2개의 약수가 존재한다.

  그래서 최소 2개의 약수는 체크하지 않아도 된다.

 

- 약수인지 체크는 절반만 살펴보면 된다.

  예를 들어, 10 의 약수를 살펴본다고 할 때, 10의 절반인 5 까지만 살펴봐도 된다.

  왜냐하면, 6,7,8,9 는 10의 약수가 될 수 없기 때문이다.

  그래서 for 문에서 loop 범위를 n/2, n의 절반으로 잡아서 불필요한 체크를 줄였다.