연습문제 > 소수 찾기

https://school.programmers.co.kr/learn/courses/30/lessons/12921

프로그래머스

 

소수 만들기라는 문제를 풀려면 소수를 찾는 방법부터 알아야 한다.

그래서 먼저 소수 찾기부터 풀어보고 다음에 소수 만들기를 풀 예정이다.

 

소수는 1과 자기 자신 외에는 어떤 수로도 나누어떨어지지 않는 1보다 큰 자연수이다.

 

가장 간단한 소수 판별 방법은 2부터 해당 숫자의 제곱근까지 모든 숫자로 나누어보는 것이.

자바스크립트에서는 Math.sqrt 를 활용하여 쉽게 소수를 찾을 수 있는데

function isPrime(num) {
    if (num <= 1) return false; // 1 이하의 수는 소수가 아님
    // 2부터 num의 제곱근까지의 모든 수로 나누어본다
    for (let i = 2; i <= Math.sqrt(num); i++) {
        if (num % i === 0) return false; // 나누어떨어지면 소수가 아님
    }
    return true; // 나누어떨어지지 않으면 소수
}

 

Math.sqrt(number);

 

console.log(Math.sqrt(16)); // 4

 

모든 합성수(소수가 아닌 수)는 제곱근 이하의 약수를 가지기 때문이다.

즉, 어떤 수 N이 소수가 아니라면, N = a * b 형태로 나타낼 수 있으며, a와 b 중 적어도 하나는 N의 제곱근 이하.

따라서 N의 제곱근까지만 검사하면, N이 소수인지 아닌지를 효율적으로 판별할 수 있다.

 

예를 들어, 29가 소수인지 판별하고자 할 때, Math.sqrt(29)는 약 5.39이고

29를 2, 3, 4, 5(5.39의 내림값)로 나누어 보면 된다.

29는 이 범위의 어떤 수로도 나누어떨어지지 않으므로, 29는 소수이다.

 

아래와 같은 다른 예시로 완전히 이해가 가능하다

17

• Math.sqrt(17) ≈ 4.12, 즉 2부터 4까지의 수로 17을 나누어 보아야 합니다.
• 17은 2, 3, 4로 나누어지지 않으므로, 17은 소수입니다.

19

• Math.sqrt(19) ≈ 4.36, 즉 2부터 4까지의 수로 19를 나누어 보아야 합니다.
• 19는 2, 3, 4로 나누어지지 않으므로, 19는 소수입니다.

23

• Math.sqrt(23) ≈ 4.79, 즉 2부터 4까지의 수로 23을 나누어 보아야 합니다.
• 23은 2, 3, 4로 나누어지지 않으므로, 23은 소수입니다.

31

• Math.sqrt(31) ≈ 5.57, 즉 2부터 5까지의 수로 31을 나누어 보아야 합니다.
• 31은 2, 3, 4, 5로 나누어지지 않으므로, 31은 소수입니다.

37

• Math.sqrt(37) ≈ 6.08, 즉 2부터 6까지의 수로 37을 나누어 보아야 합니다.
• 37은 2, 3, 4, 5, 6로 나누어지지 않으므로, 37은 소수입니다.

 

위의 제곱근 루프 소스를 활용하여 문제를 풀어보면 

function isPrime(num) {
    if (num <= 1) return false;
    for (let i = 2; i <= Math.sqrt(num); i++) {
        if (num % i === 0) return false;
    }
    return true;
}

function solution(n) {
    let count = 0;
    for (let i = 2; i <= n; i++) {
        if (isPrime(i)) count++;
    }
    return count;
}

와 같다 하지만 효율성테스트에서 통과를 못한다.

 

그래서 알고리즘을 좀 더 효율적으로 만들어보려면

결국 에라토스테네스의 체(Eratosthenes' Sieve) 알고리즘을 사용해야 한다.

이 알고리즘은 범위 내의 모든 수에 대해 소수 여부를 판별하는 대신, 소수의 배수를 차례로 제거해 나가면서

소수만을 남기는 방식으로 작동한다.

function findPrimes(n) {
  // 소수 여부를 저장할 배열 초기화 (기본적으로 모든 수를 소수로 가정)
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님

  const primes = []; // 찾은 소수를 저장할 배열

  for (let i = 2; i <= n; i++) {
    if (isPrime[i]) {
      primes.push(i); // 소수 배열에 추가
      // i의 배수는 모두 소수가 아니므로 false로 설정
      for (let j = i * i; j <= n; j += i) {
        isPrime[j] = false;
      }
    }
  }

  return primes;
}

// 사용 예:
const primesUpTo100 = findPrimes(100);
console.log(primesUpTo100);

먼저 n + 1 길이의 불리언 배열 **isPrime**을 생성하고, 모든 값을 **true**로 초기화 함

배열의 각 인덱스는 해당 인덱스 숫자의 소수 여부를 나타냄 (즉, **isPrime[2] = true**는 2가 소수).

**0**과 **1**은 소수가 아니므로 처음에 **false**로 설정.

 

이후, 2부터 시작하여 **n**까지 각 숫자에 대해 소수 여부를 판별.

어떤 수 **i**가 소수인 경우, **i**의 배수는 모두 소수가 아니므로 isPrime 배열에서 해당 배수들을 **false**로 설정.

이때, **(i * i)**부터 시작하는 이유는 **i**보다 작은 소수들에 의해 이미 **i**의 배수가 처리되었기 때문.

최종적으로 primes 배열에는 n 이하의 모든 소수가 저장되어 반환됨. 

 

최종 풀이하면

에라토스테네스의 체 알고리즘 자체에서 배열을 반환하므로 배열의 길이만 리턴하면 된다.

function solution(n) {
    const isPrime = new Array(n + 1).fill(true);
    isPrime[0] = isPrime[1] = false;
    const primes = [];

    for (let i = 2; i <= n; i++) {
        if (isPrime[i]) {
            primes.push(i);
            for (let j = i * i; j <= n; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return primes.length;
}