[BOJ] 2581번 소수

소수 << 문제 클릭!

✅문제 설명

• 입력 : 자연수 M, N (M, N은 10,000 이하의 자연수, M은 N보다 작거나 같다)

1. 자연수 M이상 N 이하의 자연수 중 소수를 모두 찾는다.
2. 소수의 합과 최솟값을 찾는다.

• 출력
  : 첫째 줄에 그 합을, 둘째 줄에 그 중 최솟값을 출력
  : M이상 N이하의 자연수 중 소수가 없을 경우는 첫째 줄에 -1을 출력한다.

❗핵심원리

• 소수 찾기
  : 주어진 M 이상에서 소수를 찾는 방법은 없을까?
  -> 없음 소수는 자기 자신과 1로만 나누어지는 수 이므로 1부터 자기자신까지 나누어서 소수를 찾아야 한다.
  -> 그렇다면 더 빨리 소수를 찾는 방법은?
  -> 소인수분해를 했을 때 1과 자기자신의 곱으로 분해되면 소수로 판단한다.

  ✅ 소수를 따로 저장하고 소수 판별에 사용하자

💻코드

1차 문제 풀이

• 1부터 M까지 소수를 구하고 M부터 N까지 소수를 찾고 더해주는 전략
• 이때 소수를 vector s에 담고 소수 판별할 때 활용한다.

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
	ios::sync_with_stdio(0); // C 표준 stream과 C++ 표준 stream의 동기화를 끊는다.
	cin.tie(0);

	int M, N;
	int min = 0;
	int sum = 0;
	vector<int> s; // 소수만 담겨있다.

	cin >> M >> N;

	s.push_back(2); // 2가 소수임을 알고 있는 가정 하에 

	for (int i = 3; i < M; i++) {
		// M 전까지 소수 담기 
		int j = 0; 
		for (; j < s.size(); j++) {
			if (i % s[j] == 0) break; // 소수 중 하나라도 나줘지면 기각
		}
		if (j == s.size()) s.push_back(i); // 소수 추가 
	}

	for (int i = M; i < N + 1; i++) {
		int j = 0;
		for (; j < s.size(); j++) {
			if (i % s[j] == 0) break; // 소수 중 하나라도 나줘지면 기각
		}
		if (j == s.size()) {
			s.push_back(i);
			if (sum == 0) min = i; // 최솟값 
			sum += i; // 합을 더해줌 
		}
	}

	if (sum == 0) {
		cout << -1;
	}
	else {
		cout << sum << "\n" << min;
	}
}

• 1차 위기 : 반례 2, 2를 -1로 출력, 그래서 N이 2일 때 2 2를 출력 후 종료
  
• 2차 위기 : 반례 1, 1을 1 1로 출력하려고 했으나 더 이상 코드가 효율적이지 못 하다는 판단 하에 뜯어 고치기로 함.

2차 문제 풀이

• 그냥 1부터 N까지 소수를 찾는다.
• 이때 소수를 vector s에 담고 소수 판별할 때 활용한다.
• 그리고 M보다 큰 소수에 대해 sum을 한다.

#include <iostream>
#include <vector>
using namespace std;

int main(void) {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int M, N = 0;
	int min = 0;
	int sum = 0;

	cin >> M >> N;

	vector<int> s; // 소수가 담겨있다. 
	s.push_back(2);

	for (int i = 1; i < N + 1; i++) {
		int j = 0;
		for (; j < s.size(); j++) {
			if (i % s[j] == 0 || i ==1) { // 1은 기각 
				if (i == 2) { // 나눠지는 수 중 2는 계속 진행시켜서 j++를 수행시킨다. 
					continue;
				}
				break;
			}
		}
		
		if (j == s.size()) {
			s.push_back(i);
			if (i >= M) { // i가 M보다 클 때 더함
				if (sum == 0) {
					min = i;
				}
				sum += i;
			}
		}
	}

	if (sum == 0) {
		cout << -1;
	}
	else {
		cout << sum << "\n" << min;
	}
}

다른 분의 문제 풀이 (클릭)

#include <iostream>
using namespace std;

int main()
{
	int max, min;
	int count = 0; // 나눠떨어지는 수의 갯수
	int nCount = 0;  // 소수 갯수
	int result = 0, minNumber;  // 합, 소수 최솟값

	cin >> min;
	cin >> max;

	for (int i = min; i <= max; i++) // min부터 max에 대해서 
	{
		for (int j = 1; j <= i; j++) // 1부터 자기자신까지 나눈다.
		{
			if (i % j == 0)
				count++;
		}

		if (count == 2) / /소수인경우
		{
			nCount++; // 소수 개수 count
			result += i; // 더함

			if (nCount == 1) // 최쵤때 
				minNumber = i;
		}
		count = 0;
	}

	if (nCount == 0)
	{
		minNumber = -1;
		cout << minNumber << endl;
	}
	else
	{
		cout << result << endl << minNumber << endl;
	}
		
	return 0;
}

• 즉 M부터 N을 i로 나누어 (i는 i=1~i = k [k = M, M+1, M+2 ,,,, N])까지 소수 판별

확실히 소수를 저장한 후 소수를 이용해 소수를 찾는 전략이 더 빠르다!