[백준 알고리즘 c++] 문제 15. 소수 찾기2 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을 출력한다.

내풀이)

#include <iostream>

using namespace std;

int main()
{

	//문제
	//	1. 최댓값과 최솟값을 지정하고 범위 안의 소수의 값의 합과 최소 소수값을 출력한다.
	// 입력
	// 1. 최댓값 n과 최솟값 m을 입력 받는다. 
	// 처리
	// 1. 소수면 합한다.
	// 2. 소수 최솟값을 구한다.
	// 3. 소수가 없으면 -1 로 처리 한다.
	// 출력

	bool sosu[10005] = { false };

	//소수 배열 만들기 => 소수 일땐 true 로 담기게 한다.
	// 1-1. 소수 의 법칙을 지정한다.
	// 1-2. 소수는 1과 자기 자신 이외에 약수를 가지지 않는 수를 이야기 한다.
	for (int sosuNum = 2; sosuNum <= 10000; sosuNum++)
	{
		bool exist = true;
		for (int j = 2; j <= 10000; j++)
		{
			//소수가 아닐때 false
			if (sosuNum != j && sosuNum % j == 0)
			{
				exist = false;
			}
		}

		if (sosuNum == 2) {
			exist = true;
		}
		sosu[sosuNum] = exist;
	}

	//입력
	int min = 0;
	int max = 0;

	cin >> min >> max;

	//큰수로 정렬한다.
	if (min > max) {
		int temp = min;
		min = max;
		max = temp;
	}

	int min_sosu = 0;
	int sosu_sum = 0;
	int sosucount = 0;
	for (int i = max; i >= min; i--)
	{
		if (sosu[i])
		{
			min_sosu = i;
			sosu_sum += i;
			sosucount++;
		}
	}
	if (min_sosu == 0)
	{
		cout << -1 << "\n";
	}
	else {
		cout << sosu_sum << "\n";
		cout << min_sosu << "\n";
	}


	return 0;
}

문제점 : 소수를 나누지 않고 , 한번에 입력처리를 할수 있다.

#include <iostream>
using namespace std;

int main() {
	int M, N;
	int sum = 0, min = -1;
	int cnt = 0;
	cin >> M >> N;

	for (int i = M; i <= N; i++) {
		for (int div = 1; div <= i; div++) {
			if (i%div == 0)
				cnt++;
		}
        //2는 자기 자신과 을 담은 2개만을 의미 한다.
		if (cnt == 2) {		//i가 소수일 때
			if (min == -1)		//저장된 소수의 최솟값이 없을 때
				min = i;
			sum += i;
		}
		cnt = 0;
	}
	if (min == -1)
		cout << -1 << '\n';
	else
		cout << sum << '\n' << min << '\n';
}