소수 찾기 - 에라토스테네스의 체

문제

numberOfPrime 메소드는 정수 n을 매개변수로 입력받습니다.

1부터 입력받은 숫자 n 사이에 있는 소수의 개수를 반환하도록 numberOfPrime 메소드를 만들어 보세요.

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

• 10을 입력받았다면, 1부터 10 사이의 소수는 [2,3,5,7] 4개가 존재하므로 4를 반환
• 5를 입력받았다면, 1부터 5 사이의 소수는 [2,3,5] 3개가 존재하므로 3를 반환

풀이

소수 관련 문제의 가장 직관적인 형태라 생각한다. 단순하게 소수를 구해서 개수를 리턴하면 된다.

소수를 구하는 알고리즘은 다양한데 그 중 가장 많이 쓰이는 에라토스테네스의 체를 사용하였다.

이 것은 간단하다. 1부터 구하고자 하는 수(n)까지 배열을 생성한다. 그리고 숫자를 대입.

예를 들어 10까지 숫자면 1, 2, 3, …10 을 생성한다. 참고로 여기서 1은 소수가 아니므로 제외하고 i = 2부터 시작하였다.(Line. 12)

그 후 특정 숫자로 나눠진다고 판단하면 그 수의 배수들은 모두 소수에서 제외한다.

예를 들어 1부터 10까지의 소수를 구하고자 할 때 2부터 탐색을 시작할 것이다.

그럼 수는 2, 3, … , 10일 건데…..

특정 수의 배수들은 모두 소수가 아니다. 왜냐.. 소수는 1과 자신만 가져야 되는데 2부터 탐색하여 특정 수를 가진다면

1과 자신을 제외한 특정 수가 약수로 있다는 뜻이기 때문이다.

1~10에서는 2의 배수인 2, 4, 6, 8, 10은 당연히 소수가 아닐 것이고(2로 나뉘니까!)

3, 6, 9 역시 3으로 나뉘기 때문에 소수가 아니다.

그럼 다음 4를 탐색해야 하는데 4는 이미 2의 배수에서 지워졌다. 따라서 for루프를 continue한다.

즉 이렇게 함으로써 조금이라도 연산량을 줄이는 것이 에라토스테네스 체 방식이다.

이게 아니라면

3에 대해 2부터 3까지 탐색하고 4에 대해 2부터 4까지 탐색하고..

숫자가 커질 수록 어마어마한 연산량이 될 것이다….

소스 코드

#include <iostream>

using namespace std;

int numOfPrime(int n)
{
  int  answer  = 0; /* 구현 시작부 */
  int* szMulti = new int[n * sizeof(int)];
  int  i       = 2, nMultiVal;
  for (i = 2; i <= n; i++)
  {
    szMulti[i] = i;
  }
  for (i = 2; i <= n; i++)
  {
    if (szMulti[i] == NULL)
      continue;
    nMultiVal = i * 2;
    for (int j = nMultiVal; j <= n; j += i)
    {
      szMulti[j] = NULL;
    }
  }
  for (i = 2; i <= n; i++)
  {
    if (szMulti[i] != NULL)
      answer++;
  }
  delete[] szMulti; /* 구현 종료부 */
  return answer;
}

int main()
{
  int testCase   = 10;
  int testAnswer = numOfPrime(testCase);
  cout << testAnswer;
}

알고리즘 문제 Level 2 | 프로그래머스