문제 풀러 가기

소수 찾기 (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. 1부터 n까지 모든 숫자를 나열한다
2. 소수와 합성수가 아닌 자연수 1을 제거한다
3. (2, 3, 5, 7)의 자신을 제외한 모든 배수들을 (1)의 나열에서 제거한다
4. 남은 수는 모두 소수다

특정 범위의 수 중 소수를 가려내는 방법으로 에라스토테네스의 체보다 빠른 방법은 없다고 한다. 그러나 하나의 자연수가 소수인지 여부를 확인하는 것은 소수판정법이라는 효율적인 도구가 있기 때문에 범위 내 소수 찾기에만 사용한다.
위 방법을 응용하여 코드를 작성하면 해답을 찾을 수 있지 않을까?

---

(3) 모범 풀이 👏🏻

출처 - jakeseo_me님의 풀이

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;
}

이 분의 코드가 명쾌하고 깔끔해서 이해하는데 많은 도움이 되었다

1. 0, 1을 제외한 n까지 모든 숫자를 나열한다

let arr = Array(n+1).fill(true).fill(false, 0, 2);

2. 2부터 n의 제곱근 까지 모든 수의 경우를 따진다

for (let i = 2; i*i <= n; i++) { ... }

3. 2,3,5,7의 배수 중 첫 값을 제외하고 모든 배수를 찾아 해당 인덱스의 값을 false로 바꾼다

for (let j = i*i; j <= n; j+=1) { ... }

4. 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;
}

---

기본에 충실한게 최고 👍