약수 구하기 (javascript)

약수란 ?

• 인수를 나누어 떨어지게 하는 수
• 어떤 정수를 나머지 없이 나눌 수 있는 정수
  • ex) 8의 약수 : 1, 2, 4, 8

약수 구하기 알고리즘

1. 단순하게 모든 수를 나눠서 약수 구하기
2. 주어진 수의 절반을 대상으로 확인하기
3. 제곱근을 사용하기

3가지 방법에 대해 정리해볼 예정이다.

1. 단순하게 모든 수를 나눠서 약수 구하기

가장 일반적인 방법이다.
1부터 주어진 수 까지 반복해가면서 나머지가 0인 값들을 구해준다.

간단하게 구현이 가능하지만, 시간 복잡도에 있어서 좋은 방법에 속하지는 않는다.

function getDivisors (num) {
	const list = [];
  
  	for (let i = 1; i <= num; i++) {
    	if (num % i === 0) list.push(i);
    }
}

2. 주어진 수의 절반을 대상으로만 확인하기

반복문의 횟수를 줄일 수 있다.
약수는 본인을 제외하고 n / 2 보다 클 수 없기 때문에, 절반값 까지만 체크해준다.

function getDivisors (num) {
	const list = [];
  
  	for (let i = 1; i <= num / 2; i++) {
    	if (num % i === 0) list.push(i);
    }
  
  	list.push(num);
}

3. 제곱근 사용하기

해당 약수를 갖고, 입력받은 값을 나누게 될 경우 나오는 결과 값 또한 약수이기 때문에 제곱근을 사용해서 약수를 구할 수 있다.

num을 100이라고 가정했을 때 Math.sqrt(100) = 10이다.
100의 약수를 10 이하의 숫자만 나열하면 [1, 2, 4, 5, 10] 이다.

하나씩 나누어 본다면 아래와 같이 값이 이뤄진다.
100 / 1 = 100
100 / 2 = 50
100 / 4 = 25
100 / 5 = 20
100 / 10 = 10

따라서 최종적으로 100의 약수는 [1, 2, 4, 5, 10, 20, 25, 50, 100] 와 같다.

function getDivisors (num) {
	const list = [];
  
  	for (let i = 1; i <= Math.sqrt(num); i++) {
    	if (num % i === 0) {
      		list.push(i);
          	// 중복된 값을 제외하기 위해서 
          	if (num / i != i) list.push(num / i);
        }
      
    }
}