소수 출력하기

돌아가기

소수(prime number)는 자신보다 작은 두 개의 자연수를 곱하여 만들 수 없는 1보다 큰 자연수입니다.

다시 말해서 1과 그 수 자신 이외의 자연수로는 나눌 수 없는 자연수를 소수라고 부르죠.

5는 2나 3, 4로 나눌 수 없기 때문에 소수입니다. 5를 이들 숫자로 나누면 나머지가 있기 때문이죠.

2부터 n까지의 숫자 중 소수만 출력해주는 코드를 작성해봅시다.

n = 10이라면 결과는 2,3,5,7이 되어야겠죠.

주의: 작성한 코드는 임의의 숫자 n에 대해 동작해야 합니다.

소수를 판단하는 알고리즘은 다양합니다.

먼저 중첩 반복문을 사용한 알고리즘을 살펴봅시다.

          범위 내 모든 숫자 i에 대해서 {
  1과 i 사이에 제수가 있는지를 확인
  있으면 => 소수가 아님
  없으면 => 소수이므로 출력해줌
}
        

레이블을 사용해 위 알고리즘을 구현한 코드는 다음과 같습니다.

let n = 10;

nextPrime:
for (let i = 2; i <= n; i++) { // 각 i에 대하여 반복문을 돌림

  for (let j = 2; j < i; j++) { // 제수(나눗수)를 찾음
    if (i % j == 0) continue nextPrime; // 소수가 아니므로 다음 i로 넘어감
  }

  alert( i ); // 소수
}

위에서 사용한 알고리즘은 최적화할 부분이 많습니다. 제수를 2와 i의 제곱근 사이에서 찾으면 좀 더 나아지겠죠. 아주 큰 n에 대해서 이차 체(Quadratic sieve)나 수 체(General number field sieve)와 같이 좀 더 어려운 수학과 복잡한 알고리즘을 이용해 소수 검색 알고리즘을 개선할 수 있을 겁니다.