[백준 BOJ] 2581번 소수 (C++/cpp)

문제 설명

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

2581번: 소수

 

접근 방법 - 소수 연산의 기본 문제

백준의 2581번 문제는 소수 연산에 있어 기본적인 원리를 묻고 있는 문제이다.

해당 문제는, 특정 범위에 속해있는 소수들의 합과 그들 중의 최솟값을 출력해야 하는 문제이다.

본래 해당 문제는 에라토스테네스의 체 알고리즘으로 해결하는 것이 정석이다.

다만, 필자가 지금부터 설명할 코드는 이 알고리즘과는 무관하며 방법이 매우 원시적이라는 점 유의하길 바란다.

만일 에라토스테네스의 체 알고리즘에 대한 설명을 원했다면 뒤로 가기를 눌러주길 바란다.

필자는 아래의 순서대로 코드를 작성하여 문제를 해결하였다.

 

코드의 실행 순서

1) 특정 범위(a, b)를 입력받는다.

 

2) 소수들의 합계를 저장할 변수 num을 0으로 초기화하여 선언한다. 잇따라, 최솟값을 저장할 변수 min을 10000으로 초기화하여 선언한다.

(입력값의 최댓값이 10000이기 때문에 최솟값 연산이 용이하도록 min을 이 값으로 초기화하였다.)

 

3) 2부터 시작하여 10000까지 숫자를 탐색하면서, 반복문을 통해 아래의 연산을 취한다.

- 다른 반복문을 통해 현재 탐색값이 소수인지를 판별한다.

해당 탐색값에 대한 약수의 개수를 측정하는데, 약수의 개수가 2개를 넘어선다면 이는 소수가 아니라고 판단하도록 한다.

- 소수로 판단되었을 경우, num에 해당 값을 더한다.

그리고 최솟값 연산도 함께 수행한다. 만약 해당 소수가 min보다 더 작다면, min에 해당 값을 저장하도록 한다.

 

4) 3)의 반복문이 모두 수행되었다면, 범위 내 소수의 유무를 파악하도록 한다.

- num의 값이 0이라면, 해당 범위 내에 소수가 없었음을 뜻한다. 따라서 이 경우엔 -1을 출력하도록 한다.

- 다만 소수가 있다고 판단되었을 시, num과 min을 순차적으로 출력하도록 한다.

 

5) 출력이 모두 수행되었다면, 실행 종료한다.

반응형

 

성공한 코드

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)
#include <iostream>
#define endl '\n'
using namespace std;

//백준 2581번 코드
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int a, b;
	cin >> a >> b;

	int num = 0;
	int min = 10000;
	for (int i = 2; i <= 10000; i++) {
		int cnt = 0;	//소수 판별
		for (int j = 1; j <= i; j++) {
			if (i % j == 0) { cnt++; }
			if (cnt > 2) { break; }
		}

		if (cnt > 2) { continue; }	// 소수가 아닐 시 넘어가기
		if (i >= a && i <= b) {
			num += i;
			if (min > i) { min = i; }
		}
	}
	if (num == 0) { cout << -1 << endl; }
	else {
		cout << num << endl;
		cout << min << endl;
	}
}

 

제출 결과

(2022.04.19 백준 2581번 문제 제출 결과)