백준 1978번 문제(소수 찾기) C++로 풀기

1978번 소수 찾기 링크

문제 요약

입력된 수들 중 소수의 개수를 구한다.

코드

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  int t;
  scanf("%d",&t);
  int innum[101]; // 입력
  for(int i=0;i<t;i++)
  {
    cin >> innum[i];
  }
  // nums의 n번째 요소가 0이면 n은 소수가 아님
  int nums[1001]; // 소수를 구하기 위한 것
  for(int j=2;j<1001;j++)
  {
    nums[j]=j;
  }
  nums[0]=0;
  for(int k=2;k<1001;k++)
  {
    if(nums[k]==0) continue;  // 소수가 아니면 넘어감
    for(int l=2*k;l<1001;l+=k)  // k의 배수는 소수가 아니다
    {
      nums[l]=0;
    }
  }
  int count=0;  // 소수 개수
  for(int h=0;h<t;h++)
  {
    if(nums[innum[h]]!=0) count+=1;
  }
  printf("%d",count);
}

풀이

에라토스테네스의 체라는 개념을 이용하는 문제이다.

위 그림이 에라토스테네스의 체를 잘 설명하는데,

1. 2부터 소수를 구하고자 하는 구간의 모든 수를 나열한다.
   • 2는 소수이므로 남기고, 자기 자신을 제외한 2의 배수를 모두 지운다.
   • 남아있는 수 가운데 3은 소수이므로 남기고, 자기 자신을 제외한 3의 배수를 모두 지운다.
   • 남아있는 수 가운데 5는 소수이므로 남기고, 자기 자신을 제외한 5의 배수를 모두 지운다.
2. 위의 과정을 계속 반복하면 구하는 구간의 모든 소수가 남는다.

이 방식을 그대로 코드로 바꿔 구현하면 된다.
문제에서 어차피 범위가 1000 이하여서, 1부터 1000까지 소수를 다 만들고, 입력을 받아 개수를 세게 했다.

주의점

에라토스테네스의 체를 이용해야 한다.