[백준] 2581번: 소수 [C/C++]

 

 

알고리즘 분류: 수학, 정수론, 소수 판정

문제 링크: https://www.acmicpc.net/problem/2581

2581번: 소수

 

---

【 문제 】

 

자연수 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을 출력한다.

 

 

---

【 풀이 】

 

M부터 N까지의 모든 자연수를 검사하는 브루트포스 알고리즘을 이용하여 풀었다.

 

• M과 N까지의 소수를 저장할 배열 선언
• M~N까지의 모든 자연수를 반복문을 사용해 하나씩 확인
• 소수인지 판별하기 위해, 1부터 확인하려는 수 까지 모든 자연수로 나누어 보기
• 이때 나누어 떨어지는 수의 개수가 2개라면, 그 수는 소수가 된다

 

 

【 C++ 소스코드 】

 

#include<iostream>
using namespace std;

int arr[10001];		//	m부터 n까지의 소수를 저장하는 배열
int main(void)
{
	int i, j, k = 0;
	int sum = 0;
	int m, n;
	cin >> m >> n;
	for (i = m; i <= n; i++)
	{
		int cnt = 0;
		for (j = 1; j <= i; j++)
		{
			if (i % j == 0)
				cnt++;
		}
		if (cnt == 2)		//	i가 소수라면 나누어 떨어지는 수는 2개가 되어야 한다.
		{
			arr[k] = i;		//	m부터 n까지의 소수들을 저장.
			k++;
		}
	}
	if (arr[0] == 0)		// 소수가 없는 경우 배열의 첫값은 0이 됨.
		cout << -1;
	else
	{
		for (i = 0; arr[i] != 0; i++)
		{
			sum += arr[i];
		}
		cout << sum << endl << arr[0];		//	최솟값은 무조건 배열의 첫값이 된다.
	}
	return 0;
}