반응형
문제는 다음과 같습니다.
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 |