2022-08-25-prime-number-2581

• toc {:toc}

문제

자연수 M 과 N 이 주어질 때 M 이상 N 이하의 자연수 중 소수인 것을 모두 골라 이들 소수의 합과 최솟값을 찾는 프로그램을 작성하시오.

예를 들어 M=60, N=100 인 경우 60 이상 100 이하의 자연수 중 소수는 61, 67, 71, 73, 79, 83, 89, 97 총 8 개가 있으므로, 이들 소수의 합은 620 이고, 최솟값은 61 이 된다.

입력

입력의 첫째 줄에 M 이, 둘째 줄에 N 이 주어진다.

M 과 N 은 10,000 이하의 자연수이며, M 은 N 보다 작거나 같다.

출력

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

단, M 이상 N 이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1 을 출력한다.

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

풀이

bool is_primeNum(int x)
{
	int i = 2;
	while(i*i<=x)
	{
		if(x%i==0)
			return false;
		i++;
	}
	return true;
}

1978: 소수 찾기에서 사용했던 소수 판별 함수를 사용.

1. m 부터 n 까지 반복문을 통해 소수인지 판별. 소수이면 sum 에 더하고 처음 찾은 값을 min 에 넣어둔다. 혹시 몰라 if 문을 통해 최솟값 판별
2. 코드를 몇 번 돌려보면서 이 문제의 요점은 1, 2 를 어떻게 처리하는가라는 것을 발견. 머리 굴리다 결국 케이스 분류를 통해 지저분하게 해결함.

홀수로 반복문을 돌리려다 복잡해진 것 같다.

#include <iostream>
 
using namespace std;
 
bool is_primeNum(int x);
 
int main()
{
	int m, n, sum=0, min = 10001, i;
	cin >> m >> n;
	
	if(m==1)
	{
		if(n>=2)
		{
			sum+=2;
			min=2;
			i = m;
		}
	}
	if(m==2)
	{
		sum+=2;
		min=2;
	}
	if(m%2==0)
	{
		i = m+1;
	}
	else
	{
		i = m;
	}
	
	for(i; i<=n; i+=2)
	{
		if(i == 1) continue;
		if(is_primeNum(i))
		{
			sum+=i;
			if(min > i)
				min = i;
		}
	}
	if(sum == 0)
		cout << -1 << endl;
	else
	{
		cout << sum << endl << min << endl;
	}
	
	return 0;
}
 
bool is_primeNum(int x)
{
	int i = 2;
	while(i*i<=x)
	{
		if(x%i==0)
			return false;
		i++;
	}
	return true;
}