<입문 100문제> Day 12 - 문자열, 정렬, 사칙연산, 수학
문제
풀이
사실 이전까지 Math.sqrt() 를 이용한 소수 구하기 문제가 꽤 있었으나, 제대로 이해하지 못해 다른 (비효율적인) 방식으로 해결하거나 애써 외면해왔다.
하지만 이 문제를 직면한 이상 더 이상 회피하지 않기로 했다.
1 부터 n (input) 까지의 소수를 순회하며 n 을 소수로 하나씩 대입하여 나누었다.
- while 문을 돌며 input / divide
- 나눠질 경우 divide = 2 로 초기화
- 나눠지지 않을 경우 2가 인수가 아니라는 것. divide+=1 (1씩 증가)
- 다 나눠서 input 이 1이 되면 반복문 탈출
※ 낮은 수부터 push 하므로 sort 로 정렬할 필요가 없다
function solution (n) {
let primeFactors = []
let devider = 2
while (n > 1) {
if (n % devider === 0) {
primeFactors.push(devider)
n /= devider
devider = 2
} else {
devider += 1
}
}
return [...new Set(primeFactors)] // .sort((a, b) => (a - b))
}해답
function solution(n) {
let pFactors = [];
for (let i = 2; i <= Math.sqrt(n); i++) {
while (n % i === 0) {
pFactors = [...pFactors, i];
n /= i;
}
}
if (n >= 2) pFactors = [...pFactors, n];
return [...new Set(pFactors)].sort((a, b) => a - b);
}해답풀이
-
소수 : 1과 자기자신만 약수로 가지는 수
- 1보다 큰 자연수 중 1과 그 자신만을 약수로 가지는 수
(1) 모든 소수의 약수의 개수는 2개이다
(2) 소수 중 짝수는 2 뿐이다 -
소인수분해
(1) 소인수 : 자연수의 인수 중에 소수인 것
(2) 소인수분해 : 자연수를 소인수의 곱으로 나타낸 것 -
모든 합성수는 그 수의 제곱근보다 작거나 같은 약수를 갖는다
어떤 큰 수를 소인수분해할 때, 그 수의 제곱근보다 큰 수로 나눌 필요가 없다. 이를 이용하면 반복작업을 통해 소인수분해하는 시간을 크게 단축할 수 있다. -
알고리즘
원리 : 작은 소수에서 n%i == 0이 성립하지 못한다면 그보다 큰 합성수는 n%i == 0가 성립하지 못하므로 n%i == 0이 성립하는 첫번째 i는 소수라는 점을 이용.
주어진 숫자 n의 소인수를 구할 경우,
1) i=2로 시작하여 i++ 하면서 n%i == 0 인지 체크한다.
2) n%i==0이 성립하는 경우 i를 소인수로 등록한 후 n은 i로 나눈 값을 저장하고 i는 i++ 하지 않고 i부터 다시 시작하도록 한다.
3) n이 1이 될 때까지 위 과정을 반복한다.
참고자료
