약수 구하는 방법 [자바스크립트 알고리즘]

javascript 약수 구하기

산에 있는 약수..

이미지는 드립ㅎㅎ

 

 

javascript로 약수 구하는 법을 알아보자!

 

약수 = 인수를 나누어 떨어지게 하는 수

 

 

처음에는 먼저 단순한 방법인

 

모든 수를 나눠서 구하는 법

function solution (num) {
    let answer = [];
    for(let i = 1 ; i <= num ; i++){
        if(num % i === 0) answer.push(i);
    }
    return answer;
}

1부터 num 까지 반복하면서 나머지가 0인 값들을 배열에 넣어가는 것이다.

하지만 시간복잡도에 있어서 좋지는 않은 방법이다.

 

 

 

주어진 수의 절반만 돌려서 구하기

function solution (num) {
    let answer = [];
    for(let i = 1 ; i <= num/2 ; i++){
        if(num % i === 0) answer.push(i);
    }
    return [...answer, num];
}

약수는 본인을 제외하고서는  num/2 보다 클 수가 없기 때문에 절반까지만 반복문을 돌려주는 것이다.

나머지가 0 인 값을 넣어주고 마지막에 num (본값) 을 넣어준다.

 

그다음 다른 방법은 제곱근을 활용하는 것이다.

 

 

 

제곱근을 사용해서 구하기

function solution (num) {
    let answer = [];
    for(let i = 1 ; i <= Math.sqrt(num) ; i++){
        if(num % i === 0) {
        	answer.push(i);
            if(num / i != i) answer.push(num / i);
        }
    }
    return answer
}

num 의 값이  100이라고 했을 때  Math.sqrt(num)의 값은 10 이 나온다.

10까지만 반복문을 돌려서 약수를 구하지만  [1,2,4,5,10]

if 문을 추가해서 해당 입렵 받은 값을 나누어서 나오는 값도 약수이다.

 

100 / 1 = 100

100 / 2 = 50

100 / 4 = 24

100 / 5 =20

100 / 10 = 10

 

조건에 if문을 추가하여서 나누었을때 i랑 다르면 넣었기 때문에 (중복제거)

(중복제거하는 법은 new Set 이라는 내장객체를 활용해서 할 수 도 있다.)

 

최종적으로 나오는 배열은

[1,100,2,50,4,25,5,20,10] 이렇게 나온다.

 

[1,100,2,50,4,25,5,20,10].sort((a , b) => a - b)

하지만 순서가 위에 두가지 방법과는 다르게 나온다.

그래서 정렬을 따로 해줘야한다.

sort() 함수를 사용해서 오름차순으로 바꿔 줄 수 있다.

[1,2,4,5,10,20,25,50,100] 이렇게 된다.