[C++] 백준 2581번 소수

1. 문제이해

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

2581번: 소수

 

M 이상 N 이하의 자연수 중 소수인 것을 찾아

해당 값들의 합과 값들 중 최솟값을 출력하는 것이 목표이다.

 

 

 

2. 문제풀이

 

M 이상 N 이하의 소수를 모두 찾아 해당 값들의 합과 최솟값을 출력하는 문제이다.

이전에도 비슷한 문제를 풀이한 적이 있어서, 해당 방법과 비슷한 방법으로 풀이했다.

 

제곱근 값(루트값)을 기준으로, 앞의 있는 수들과 뒤에 있는 수들은 서로 짝을 이루므로,

제곱근 값을 기준으로 앞에 있는 수들로 나눠진다면, 뒤에 있는 수들 또한 나눠지게 된다.

이렇듯 제곱근 값(루트값)을 기준으로 앞에 있는 수들만 검사해,

for문을 통해 검사해야 하는 범위를 절반으로 줄여 시간초과를 해결하는 방식을 이용했다.

 

위 방법을 이용해 범위 내의 소수를 모두 구한 뒤 벡터값에 집어넣고,

값들을 모두 더하고, 첫번째 값(가장 작은 값)을 출력하는 식으로 코드를 작성했다.

자세한 풀이방식은 아래 포스팅을 참고하자.

 

https://beginnerdeveloper-lit.tistory.com/65

[C++] 백준 1929번 소수 구하기

 

 

 

3. 소스코드

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

int main() {
	vector <int> v;
	int M, N;
	int not_prime_num;
	int root;	// 제곱근
	int sum = 0;

	cin >> M >> N;
	for (int i = M; i <= N; i++) {
		not_prime_num = 0;
		root = (int)sqrt(i);

		// 1은 소수가 아니므로 따로 count
		if (i == 1) {
			not_prime_num++;
			continue;
		}

		// 2부터 제곱근값 전까지 나눠지는 수가 있다면 소수가 아님
		for (int j = 2; j <= root; j++) {
			if (i % j == 0) {
				not_prime_num++;
				break;
			}
		}

		// 약수의 개수가 0개 = 소수이므로 벡터에 저장
		if (not_prime_num == 0) {
			v.push_back(i);
		}
	}

	// 만약 범위 내에 소수가 없다면, -1 출력
	if (v.empty()) {
		cout << "-1";
	}

	else {
		for (int i = 0; i < v.size(); i++) {
			sum += v[i];
		}
		cout << sum << "\n" << v[0];
	}
	return 0;
}

이전 포스팅과 풀이방식은 동일하다.

제곱근 값을 이용해 해당 범위 내의 소수들을 모두 구해 벡터에 저장해주었다.

만약 소수인 것이 없다면, -1 을 출력하고,

아니라면 벡터값에 저장된 소수들의 합과 최솟값(v[0])을 출력하도록 했다.

 

주석이 없는 코드는 왼쪽 아래 더보기를 참고 바랍니다.😊

<주석 없는 코드>

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

int main() {
	vector <int> v;
	int M, N;
	int not_prime_num;
	int root;	
	int sum = 0;

	cin >> M >> N;
	for (int i = M; i <= N; i++) {
		not_prime_num = 0;
		root = (int)sqrt(i);

		if (i == 1) {
			not_prime_num++;
			continue;
		}

		for (int j = 2; j <= root; j++) {
			if (i % j == 0) {
				not_prime_num++;
				break;
			}
		}

		if (not_prime_num == 0) {
			v.push_back(i);
		}
	}

	if (v.empty()) {
		cout << "-1";
	}

	else {
		for (int i = 0; i < v.size(); i++) {
			sum += v[i];
		}
		cout << sum << "\n" << v[0];
	}
	return 0;
}

 

 

---

이전 문제에 대해 확실한 풀이방법을 알고 있어서 쉽게 풀이 가능한 문제였다.

전에거를 안 풀어봤다면 어려웠을 것 같다..😥

문제에 대한 질문이나 지적은 언제나 감사히 받고 있습니다.😊