Skip to content

소수_찾기.md

Latest commit

 

History

History
136 lines (102 loc) · 5.61 KB

소수_찾기.md

File metadata and controls

136 lines (102 loc) · 5.61 KB

소수 찾기

프로그래머스

문제

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하는 함수, solution을 만들어 보세요.

소수는 1과 자기 자신으로만 나누어지는 수를 의미합니다. (1은 소수가 아닙니다.)

제한 조건

  • n은 2이상 1000000이하의 자연수입니다.

첫 번째 제출 코드

const solution = (n) => {
  let count = 0;
  for (let i = 2; i <= n; i++) {
    let isPrime = true;
    for (let j = 2; j <= Math.sqrt(i); j++) {
      if (i % j === 0) {
        isPrime = false;
        break;
      }
    }
    if (isPrime) count++;
  }
  return count;
};

기본 전제

  • 소수 판별에서 가장 일반적인 방법은 1부터 그 수의 제곱근까지 1씩 증가시키며 그 수를 나누어보는 것이다. 만약 어떤 수로도 나누어지지 않는다면 그 수는 소수다.
  • 1부터 n까지 판별을 반복하며 만약 어떤 수가 소수로 판별되면 카운트를 1씩 올린다.

풀이 과정

  1. 소수 개수를 셀 count 변수를 0으로 초기화한다.
  2. 2부터 n까지 for문을 돌려 범위 내의 모든 수를 검사한다.
    • 1은 소수가 아니므로 범위에서 제외한다.
  3. isPrime을 true로 초기화한다.
  4. 2부터 현재 소수 여부를 판별하고자 하는 값의 양의 제곱근까지 1씩 증가시키며 현재 수를 나눠본다.
    • 만약 하나라도 나누어떨어지게 만드는 수가 범위 안에 존재한다면 isPrime에 false를 할당하고 내부 반복문을 탈출한다.
  5. 내부 반복문이 끝난 후 만약 isPrime이 true라면(범위 내에서 현재 수를 나누어떨어지게 만드는 수가 존재하지 않았다면) count를 1 증가시킨다.
  6. 범위 내의 모든 수에 대해 같은 작업이 끝나면 최종적으로 count를 반환한다.

문제점

  • 효율성 테스트를 통과하긴 했지만 이중반복문으로 인해 시간복잡도가 증가한다는 점, 특히 불필요한 검사가 계속되는 것(어떤 소수를 발견했다면 그 소수의 배수들은 자동으로 소수 목록에서 제외되어야 한다.)이 마음에 걸렸다.
  • 또한 소수 판별은 오래전부터 존재했던 문제이므로 소수인지의 여부를 판별할 수 있는 보다 효율적인 알고리즘이 분명 존재할 것이라고 생각했다.

두 번째 제출 코드

const solution = (n) => {
  let primeCount = 0;
  let numbers = [];
  for (let i = 2; i <= n; i++) numbers.push(i);

  while (numbers.length > 0) {
    const primeNumber = numbers.shift();
    primeCount++;
    if (primeNumber ** 2 > n) continue;
    numbers = numbers.filter((number) => number % primeNumber !== 0);
  }

  return primeCount;
};

기본 전제

  • '에라토스테네스의 체' 알고리즘을 사용한다.
    • 자연수 목록에서 가장 작은 수를 소수라고 가정한다(1은 제외).
    • 목록 안에서 그 수를 제외한 해당 수의 배수를 모두 제거한다.
    • 다음으로 작은 수에 대해 같은 방법을 적용한다.
    • 다음으로 작은 수가 n의 제곱근보다 크면 종료한다(n의 제곱근보다 큰 수의 배수는 범위를 초과하므로.).
    • 목록에 남아있는 수가 해당 범위에 존재하는 소수이다.

풀이 과정

  • 소수 개수를 카운팅 할 primeNumber를 0으로 초기화한다.
  • numbers 배열에 2부터 n까지의 자연수를 담아 초기화한다.
  • numbers의 길이가 0이 될 때까지 밑의 처리를 반복한다.
    • numbers에서 가장 작은 수를 제거하여 primeNumber에 저장한다.
    • 소수 카운트를 1 올린다.
    • 만약 primeNumber의 제곱이 n보다 크면 다음 반복으로 넘어간다.
    • 아니라면 numbers에 filter() 메소드를 사용하여 primeNumber의 배수를 모두 제거한다.
  • 해당 작업이 모두 끝나면 소수 카운트를 반환한다.

문제점

  • 효율성 테스트에서 탈락했다.
    • filter 메소드를 사용하여 완전탐색하는 과정에서 소수의 배수를 미리 제외하는 장점을 잃어버렸다.
    • 어떤 수의 배수는 미리 계산할 수 있으므로 완전탐색할 필요가 없기 때문이다.

세 번째 제출 코드

const solution = (n) => {
  const isPrimeMap = new Array(n + 1).fill(true);
  for (let i = 2; i <= n ** 0.5; i++) {
    if (isPrimeMap[i]) {
      for (let j = i * 2; j <= n; j += i) isPrimeMap[j] = false;
    }
  }
  let cnt = 0;
  for (let i = 2; i <= n; i++) {
    if (isPrimeMap[i]) cnt++;
  }
  return cnt;
};

풀이 과정

  1. Array 객체 생성자를 사용하여 n + 1개의 요소를 true로 초기화한다.
  • 배열의 인덱스를 소수 판별 대상으로 사용할 것이기 때문에 n + 1개의 요소를 만든 후, 인덱스 1부터 n까지 사용한다.
  1. 2부터 n의 제곱근 이하까지 반복문을 돌린다.
  • 만약 해당 인덱스의 값이 true라면 해당 수는 소수로 간주하고 해당 수의 배수를 모두 제거한다.
    • 해당 수의 2배수부터 시작하여 n 이하의 배수에 해당하는 인덱스까지를 모두 false로 바꾼다.
  1. 판별 작업이 끝난 후, 값이 true인 요소의 개수를 센다.
  2. 최종적으로 센 값을 반환한다.

알고 가자

  • 특정 수가 소수인지 판별할 떄는 2부터 해당 수의 제곱근까지 나눠보기, 특정 범위에서 소수를 찾아낼 때는 에라토스테네스의 체 쓰기.
  • 이 두 방법은 공식처럼 외우고 있어도 나쁘지 않을 것 같다.