약수의 개념
- 약수란 인수를 나누어 떨어지게 하는 수이다.
- 모든 자연수는 1과 자기자신을 약수로 가짐(반존수)
- 반존수만 있는 수는 소수이다.
- 0의 약수는 존재하지 않는다.
- 0은 모든 수의 약수가 아니다.
- 약수는 본인을 제외하고 n/2보다 클 수 없다.
- 자연수를 제곱근의 약수로 나누면, 약수이며 제곱근의 약수 또한 자연수의 약수이다.
약수를 구하는 여러가지 방법
1. 단순 계산
- 1에서 주어진 수까지 반복하며 나머지가 0인 값을 구해줌
function solution(n) {
var answer = 0;
for(let i = 1; i < n + 1; i++) {
if(n % i === 0) {
answer += i
}
}
return answer;
}2. n의 절반을 대상으로만 계산
- 약수는 본인을 제괴하고 n/2보다 클 수 없다는 점을 이용하여 계산
function solution(n) {
var answer = n;
for(let i = 1; i <= n/2; i++) {
if(n % i === 0) {
answer += i
}
}
return answer;
}3. 제곱근(Math.sqrt)을 사용한 계산
- 자연수를 제곱근의 약수로 나누면, 약수이며 제곱근의 약수 또한 자연수의 약수라는 점을 이용
- 가장 빠른 시간 복잡도를 가짐
function solution(n) {
var answer = 0;
for(let i = 1; i <= Math.sqrt(n); i++) {
// console.log(`i: ${i}`)
// console.log(n % i === 0)
if(n % i === 0) {
answer += i
if(n / i !== i) {
answer += n / i
}
}
}
return answer;
}✨ 참고
