2581 번 : 소수

문제는 다음과 같습니다.

https://www.acmicpc.net/problem/2581

2581번: 소수

 

풀이 코드는 다음과 같습니다.

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
	int n,m;
	cin>>n>>m;
	bool check[10001]{false};
	check[0]=true;
	check[1]=true;
	for(int i{2};i<=sqrt(m);i++)
	{
		if(!check[i])
		{
			int temp{2};
			while(temp*i<=m)
			{
				check[temp*i]=true;
				temp++;
			}
		}
		
	}
	int sum{0};
	int mini;
	for(int i{n};i<=m;i++)
	{
		if(!check[i])
		{
			if(sum==0)
				mini=i;
			sum+=i;
		}
	}
	if(sum==0)
		cout<<-1;
	else
		cout<<sum<<"\n"<<mini;
}

 

에라토스테네스의 체를 이용해서 소수를 찾았으며 특정 범위가 주어지므로 그 범위까지만 찾으면 됩니다.

원소 모두를 기억할 필요가 없어서 vector를 사용하지 않고 조건문으로 소수 중의 최솟값을 찾았습니다.