약수 구하기

약수를 구하는법

1. 1부터 구하는 수까지 전부 나머지를 구해보는 방식
   시간복잡도 : O(N)

let num = 10;
let sum = 0;
for(let i = 1; i<= num; i++){
	if(num%i===0)sum++;
}

2. num/2이상의 수는 약수에서 나오지 않기때문에 사용할 수 있는 방식
   시간복잡도 : O(N)

let num = 10;
let sum = 0;
for(let i = 1; i<= num/2; i++){
	if(num%i===0)sum++;
}
sum++; //자기 자신은 더해줘야한다.

3. 🔆
   시간복잡도 : O(sqrt(N))

let num = 100;
let sum = 0;
for( let i = 1; i*i <= num; i++){
	if(i*i=== num)sum++;
    else if(num%i === 0)sum+=2;
}

i*i === num 이라는 뜻은 제곱수라는 뜻. 따라서 10*10 = 100일때 약수는 10 한개만 포함된다.
i = 1일 때 100/1 = 100으로 100이 대응된다.
i = 2일 때 100/2 = 50으로 50이 대응된다.
따라서 num%i === 0일때의 약수는 2개씩을 의미하므로 2를 더해주면 된다.