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

2581번 소수 링크

---

문제 요약

M이상 N이하의 자연수 중 소수인 것을 모두 찾아 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력한다.
단, M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

---

코드

#include <iostream>
#include <cmath>

using namespace std;

int main()
{
  int m,n;
  scanf("%d",&m);
  scanf("%d",&n);
  int nums[10001]={0,};
  for(int j=2;j<10001;j++)
  {
    nums[j]=j;
  }
  for(int k=2;k<10001;k++)  // 에라토스테네스의 체
  {
    if(nums[k]==0) continue;
    for(int l=2*k;l<10001;l+=k)
    {
      nums[l]=0;
    }
  }
  int sum=0;
  int small=0;
  for(int h=n;h>=m;h--) // 최소의 소수와 소수들의 합을 찾음
  {
    if(nums[h]!=0)
    {
      sum+=nums[h];
      small=nums[h];
    }
  }
  if(sum==0)
  {
    printf("%d",-1);
  }
  else
  {
    printf("%d\n",sum);
    printf("%d",small);
  }
}

---

풀이

에라토스테네스의 체를 이용해 문제의 범위인 10000까지 소수를 전부 구하고 시작했다.

---

주의점

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