약수를 구하는법
- 1부터 구하는 수까지 전부 나머지를 구해보는 방식
시간복잡도 : O(N)
let num = 10;
let sum = 0;
for(let i = 1; i<= num; i++){
if(num%i===0)sum++;
}
- num/2이상의 수는 약수에서 나오지 않기때문에 사용할 수 있는 방식
시간복잡도 : O(N)
let num = 10;
let sum = 0;
for(let i = 1; i<= num/2; i++){
if(num%i===0)sum++;
}
sum++; //자기 자신은 더해줘야한다.
- 🔆
시간복잡도 : 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를 더해주면 된다.
'코테 준비 > 알고리즘' 카테고리의 다른 글
전체 탐색 - 조합 전체 탐색 (비트 연산 이용) (0) | 2024.08.05 |
---|---|
숫자의 표현 문제 (0) | 2024.08.05 |
나머지 연산의 특징 (0) | 2024.08.05 |
뉴턴-랩슨 방법 (sqrt를 쓰지 않고 제곱근을 구하는 법) (0) | 2024.08.05 |
시간복잡도 (0) | 2024.08.05 |