백준 문제풀이

2581 번 : 소수

하다블 2023. 4. 27. 18:03
반응형

문제는 다음과 같습니다.

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

 

2581번: 소수

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

www.acmicpc.net

 

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

#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를 사용하지 않고 조건문으로 소수 중의 최솟값을 찾았습니다.

반응형

'백준 문제풀이' 카테고리의 다른 글

3009 번 : 네 번째 점  (0) 2023.04.27
1085 번 : 직사각형에서 탈출  (0) 2023.04.27
9506 번 : 약수들의 합  (0) 2023.04.26
2501 번 : 약수 구하기  (0) 2023.04.26
5086 번 : 배수와 약수  (0) 2023.04.26