소수 찾기 (Lv. 1)
(1) 문제
1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.
소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)
(1-1) 제한 조건
- n은 2이상 1000000이하의 자연수입니다.
(1-2) 입출력 예
| n | result |
|---|---|
| 10 | 4 |
| 5 | 3 |
(1-3) 입출력 예 설명
입출력 예 #1
1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
입출력 예 #2
1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환
(2) 풀이 과정
(2-1) 소수 구하는 알고리즘
소수 n은 1과 n으로만 나누어진다
function isPrime(number) {
let isPrime = true;
for (let i = 2; i <= number / 2; i++) {
if (number % i === 0) {
isPrime = false;
break;
};
};
return isPrime ? 'Prime' : 'NOT a Prime';
}
console.log(isPrime(2)); // Prime
console.log(isPrime(3)); // Prime
console.log(isPrime(4)); // Not a Prime
console.log(isPrime(5)); // Prime
console.log(isPrime(6)); // Not a Prime
console.log(isPrime(7)); // Prime
console.log(isPrime(8)); // Not a Prime
console.log(isPrime(9)); // Not a Prime
console.log(isPrime(11)); // Prime약수는 정수의 절반 이상이 될 수 없으며, 소수는 약수가 1과 자신밖에 없으니 1 < 약수 < (input/2) 사이에 단 하나라도 나누어 떨어지는 숫자가 존재한다면 해당 수는 소수가 아니다
(2-2) 2부터 n까지의 수 중에서 소수를 찾기
같은 원리로 소수에 해당하는 2부터 정수 limit까지 모든 소수를 찾아보자
function isPrime(limit) {
const primes = [];
for (let i = 2; i <= limit; i++) {
primes.push(i);
for (let j = 2; j <= i / 2; j++) {
if (i % j === 0) {
primes[i - 2] = false;
break;
};
};
}
return primes.filter(e => e !== false);
}
// limit
console.log(isPrime(11));
// expected output: [2, 3, 5, 7, 11]
console.log(isPrime(32));
// expected output: [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31]limit까지 2부터 모든 숫자를 채워넣은 배열에서 소수에 해당하지 않는 것을 false로 바꾸고, 소수만 걸러진 배열에서 false를 제거하여 반환한다. 반환 값에 length만 붙이면 문제에 대한 답은 될 수 있다.
그러나 모든 정수를 일일히 넣어 대조하기 때문에 O(N^2) 수준으로 매우 비효율적이다.
for (let j = 2; j * j <= i / 2; j++)약수의 범위를 sqrt(n)까지만 구하여 대조하면 성능은 조금 나아지지만 유의미하진 않다. 더 효율적인 방법을 찾아야 한다.
(2-3) 에라토스테네스의 체
에라토스테네스의 체는 에라토스테네스라는 고대 수학자가 만든 소수를 가장 빨리 찾는 도구라고 한다. 방법은 아래와 같다. 자료 출처 - wikipedia
- 1부터 n까지 모든 숫자를 나열한다
- 소수와 합성수가 아닌 자연수 1을 제거한다
- (2, 3, 5, 7)의 자신을 제외한 모든 배수들을 (1)의 나열에서 제거한다
- 남은 수는 모두 소수다
특정 범위의 수 중 소수를 가려내는 방법으로 에라스토테네스의 체보다 빠른 방법은 없다고 한다. 그러나 하나의 자연수가 소수인지 여부를 확인하는 것은 소수판정법이라는 효율적인 도구가 있기 때문에 범위 내 소수 찾기에만 사용한다.
위 방법을 응용하여 코드를 작성하면 해답을 찾을 수 있지 않을까?
(3) 모범 풀이 👏🏻
let solution = (n) => {
// 0과 1의 자리를 제외하고 모두 n+1만큼 true로 채운 배열 만듦
let arr = Array(n+1).fill(true).fill(false, 0, 2);
// 2부터 n의 제곱근 만큼만 수를 대조하며 약수를 찾는다
for(let i=2; i*i<=n; i++){
/* j가 i의 제곱부터 시작하겠다는 것은
2, 3, 5, 7은 제외하고 그 배수들만 제거
j+=i는 첫 값을 제외한 i의 배수만큼 매칭 */
for(let j=i*i; j<=n; j+=i){
// 배열 내 해당 인덱스는 false 반환
arr[j] = false;
};
};
// true값만 세어 최종값을 반환한다
return arr.filter(e => e).length;
}이 분의 코드가 명쾌하고 깔끔해서 이해하는데 많은 도움이 되었다
0,1을 제외한n까지 모든 숫자를 나열한다let arr = Array(n+1).fill(true).fill(false, 0, 2);
2부터n의 제곱근 까지 모든 수의 경우를 따진다for (let i = 2; i*i <= n; i++) { ... }
2,3,5,7의 배수 중 첫 값을 제외하고 모든 배수를 찾아 해당 인덱스의 값을false로 바꾼다for (let j = i*i; j <= n; j+=1) { ... }
true값만 세어 최종 값을 반환한다return arr.filter(e => e).length;
수학 도구를 알아내도 코드로 풀어내기는 아직 벅차다.
이 분의 코드처럼 다른 사람들도 이해하기 쉽고, 코드 자체로도 높은 효율성을 내는 코드가 클린 코드라는 생각이 들었다.
많이 노력해야겠다.
// 👏🏻 👏🏻 👏🏻
//
function solution(n) {
let arr = Array(n+1).fill(true).fill(false, 0, 2);
for (let i=2; i*i <= n; i++) {
for (let j=i*i; j <= n; j+=i) {
arr[j] = false;
}
}
return arr.filter(e => e).length;
}
기본에 충실한게 최고 👍
