제곱근을 활용하여 약수의 개수 구하기

안녕하세요, 오늘은 어떤 정수의 약수의 개수를 구할 때 제곱근을 활용하는 방법에 대해 알아보겠습니다.

 

제곱근을-활용하여-약수의-개수-구하기

---

 
ㅡㅡㅡㅡㅡㅡㅡ목차ㅡㅡㅡㅡㅡㅡㅡ

 
 
 
1. 약수란?
 
2. 약수의 개수 구하는 방법
 
3. 제곱근을 활용하여 약수의 개수 구하는 방법

1. 원리
2. 주의사항 (제곱근 자체가 정수일 경우)
3. 예시
4. 프로그래밍시 사용방법
   1. 파이썬(python)
   2. 자바(java)
   3. C++(cpp)

---

1. 약수란?

- 약수란 어떤 수를 나누어 떨어지게 하는 수를 말합니다.

 

예를 들어, 12의 약수는 1, 2, 3, 4, 6, 12입니다.

왜냐하면 12를 1, 2, 3, 4, 6, 12로 나누면 나머지가 0이기 때문입니다.

 

---

2. 약수의 개수 구하는 방법

- 약수의 개수를 구하는 가장 간단한 방법은 모든 수를 하나씩 나눠보는 것입니다.

 

예를 들어, 12의 약수의 개수를 구하려면 1부터 12까지 모두 나눠보고 나누어 떨어지는 수의 개수를 세면 됩니다. 하지만 이 방법은 수가 커질수록 시간이 많이 걸립니다.

 

예를 들어, 1000의 약수의 개수를 구하려면 1000번이나 나눠야 합니다. 그래서 더 빠른 방법이 필요합니다. 그 방법이 바로 제곱근을 활용하는 방법입니다.

 

---

3. 제곱근을 활용하여 약수의 개수 구하는 방법

3.1. 원리

- 어떤 수의 제곱근보다 작은 약수는 큰 약수는 서로 짝을 이룹니다.

 

예를 들어, 12의 제곱근(√12)은 약 3.46입니다. 그러면 제곱근보다 이하인 약수는 1, 2, 3이고, 이들의 짝이 되는 큰 약수는 각각 12, 6, 4입니다.

 

- 따라서 제곱근보다 이하인 약수의 개수에 2를 곱하면 약수의 개수를 구할 수 있습니다.

 

예를 들어, 위에서 구한 제곱근보다 작은 약수의 개수인 3에 2를 곱하면 약수의 개수인 6을 구할 수 있습니다.

 

하지만 이 방법에는 한 가지 주의할 점이 있습니다. 바로 제곱근 자체가 정수일 경우입니다.

 

 

 

3.2. 주의사항 (제곱근 자체가 정수일 경우)

예를 들어, 16의 제곱근(√16)은 정확히 4입니다. 그러면 제곱근보다 이하인 약수는 1, 2, 4이고, 이들의 짝이 되는 큰 약수는 각각 16, 8, 4입니다.

 

하지만 여기서 제곱근 자체인 4도 약수입니다. 그러므로 제곱근보다 이하인 약수의 개수에만 2를 곱하면 중복되는 것이 있습니다.

 

- 따라서 이 경우에는 제곱근보다 이하인 약수의 개수에 2를 곱한 후에 다시 1을 빼줘야 합니다.

 

예를 들어, 위에서 구한 제곱근보다 이하인 약수의 개수인 3에 2를 곱하고 1을 빼주면 약수의 개수인 5를 구할 수 있습니다.

 

 

 

3.3. 예시 및 프로그래밍시 사용방법

이제 제곱근을 활용하는 방법을 실제로 적용해 보겠습니다.

 

# 예시 1) 24의 약수의 개수를 구하세요.

# 해설

- 24의 제곱근 (√24) 은 약 4.90입니다. 그러면 제곱근보다 이하인 약수는 1, 2, 3, 4이고, 이들의 짝이 되는 큰 약수는 각각 24, 12, 8, 6입니다. 따라서 제곱근보다 이하인 약수의 개수인 4에 2를 곱하면 약수의 개수인 8을 구할 수 있습니다.

 

# 예시 1) 36의 약수의 개수를 구하세요.

# 해설

- 36의 제곱근 (√36) 은 정확히 6입니다. 그러면 제곱근보다 이하인 약수는 1, 2, 3, 4, 6이고, 이들의 짝이 되는 큰 약수는 각각 36, 18, 12, 9, 6입니다. 하지만 여기서 제곱근 자체인 6도 약수입니다. 그러므로 제곱근보다 이하인 약수의 개수인 5에 2를 곱한 후에 다시 1을 빼면 약수의 개수인 9를 구할 수 있습니다.

 

 

 

3.4.  프로그래밍시 사용방법

1. 파이썬(python)

# python 코드

# n의 약수의 개수를 구하는 함수
def count_divisors(n):

	# n의 약수의 개수를 구하는 함수
	count = 0 # 약수의 개수를 저장할 변수
  
  	# 1부터 n의 제곱근까지 반복
  	for i in range(1, int(n**0.5) + 1):
  
  		# i가 n의 약수라면
    	if n % i == 0:
    	
      	count += 2
      
      	if i == n//i: # i와 n//i가 같다면 (즉, i가 제곱근이라면)
        
        	count -= 1 # 중복되는 약수이므로 count에서 1을 
        
  	# count를 반환
  	return count

# 예시
print(count_divisors(24)) # 8을 출력
print(count_divisors(36)) # 9를 출력

 

2. 자바(java)

// java 코드
public class DivisorCounter {

  	// n의 약수의 개수를 구하는 클래스
  	public static int countDivisors(int n) {
  
    	// n의 약수의 개수를 구하는 메소드
    	int count = 0; // 약수의 개수를 저장할 변수
    	
        // 1부터 n의 제곱근까지 반복
    	for (int i = 1; i <= Math.sqrt(n); i++) {
        	
            // i가 n의 약수라면
            if (n % i == 0) {
      
      			// i와 n/i가 약수이므로 count에 2를 더함
        		count += 2;
        
        		// i와 n/i가 같다면 (즉, i가 제곱근이라면)
        		if (i == n/i) {
        			
                    // 중복되는 약수이므로 count에서 1을 뺌
          			count -= 1;
        		}
      		}
    	}
    
    	return count; // count를 반환
  	}

  	// 예시
  	public static void main(String[] args) {
    
  		System.out.println(countDivisors(24)); // 8을 출력
    	System.out.println(countDivisors(36)); // 9를 출력
  	}
}

 

3. C++(cpp)

// c++ 코드
#include <iostream>
#include <cmath>
using namespace std;

// n의 약수의 개수를 구하는 함수
int count_divisors(int n) {

	int count = 0; // 약수의 개수를 저장할 변수
  
  	// 1부터 n의 제곱근까지 반복
  	for (int i = 1; i <= sqrt(n); i++) {
  
  		// i가 n의 약수라면
    	if (n % i == 0) {
    
    		// i와 n/i가 약수이므로 count에 2를 더함
        	count += 2;
        
        	// i와 n/i가 같다면 (즉, i가 제곱근이라면)
        	if (i == n/i) {
        
        	// 중복되는 약수이므로 count에서 1을 뺌
        	count -= 1;
      		}
    	}
  	}
  	return count; // count를 반환
}

// 예시
int main() {
  	cout << count_divisors(24) << endl; // 8을 출력
  	cout << count_divisors(36) << endl; // 9를 출력
}