[백준 BOJ] 2960번 에라토스테네스의 체 (C++/cpp)

문제 설명

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

2960번: 에라토스테네스의 체

 

접근 방법 - 에라토스테네스의 체 알고리즘 기본 문제

백준의 2960번 문제는 에라토스테네스의 체 알고리즘의 기본 문제이다.

해당 문제는, 에라토스테네스의 체 알고리즘을 설명하고 있는데 이를 코드로 작성하여 응용해볼 것을 요구하고 있다.

해당 알고리즘은 간략하게 아래의 원리대로 구동된다.

- 0과 1은 소수가 아니다.
- "소수의 배수들은 자기 자신을 제외하고는 모두 소수가 아니다."
 ex) 2는 소수이지만 2의 배수들인 4, 6, 8 등은 소수가 아니다.

이 알고리즘에 대한 자세한 내용은 문제의 설명을 참고하길 바란다.

소수의 기본적인 개념과 위의 원리를 이해했다면, 해당 문제는 어렵지 않게 풀 수 있을 것으로 예상된다.

만일 코드를 작성하는 데에 어려움을 겪고 있다면, 아래의 설명과 코드를 참고해보길 바란다.

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

 

코드의 실행 순서

1) 입력값의 최대 범위만큼의 크기를 가진 배열(arr)을 전역 변수로 선언해둔다.

 

2) 해당 문제는, 1부터 n까지의 숫자에 대해 에라토스테네스의 체 알고리즘을 수행할 때 k번째로 지워질 숫자를 출력해야 하는 문제이다.

여기서, n과 k를 순차적으로 입력받는다.

 

3) 지워지는 숫자의 순서를 카운팅할 변수 cnt를 0으로 초기화하여 선언한다.

 

4) 반복문을 통해, 배열 번호들에 따른 arr의 배열값들을 탐색하며 아래의 연산을 취한다.

- 만일 현재 탐색값이 0이라면, 이 배열 번호의 값은 아직 연산이 되지 않은 값이다.

따라서 이 경우엔, 해당 배열값을 1로 변경하며 cnt의 값에 1을 추가한다.

(현재 탐색값이 1이라면, 이 배열 번호의 값은 연산이 완료된 경우이기 때문에 다음 차례의 반복문을 수행하도록 한다.)

- 위에서 배열값을 변경했다면, 이의 배수들에 대한 연산을 취하도록 한다.

배수들의 배열값들을 오름차순으로 1로 변경하며, 여기서 또한 순차적으로 cnt에 1을 더하도록 한다.

- cnt의 값과 k의 값이 같아질 때까지 위 연산들을 수행한다.

만일 이 조건을 만족하는 순간이 온다면, 현재 탐색값을 출력한다.

 

5) 출력이 수행되었다면, 즉시 실행 종료하도록 한다.

반응형

 

성공한 코드

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

//백준 2960번 코드
int arr[1001];
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);	cout.tie(NULL);

	int n, k;
	cin >> n >> k;

	int cnt = 0;
	for (int i = 2; i <= n; i++) {
		if (arr[i] == 0) {
			arr[i] = 1;	cnt++;
			if (cnt == k) {
				cout << i << endl;
				return 0;
			}
		}
		else { continue; }
		for (int j = i + 1; j <= n; j++) {
			if (j % i == 0 && arr[j] == 0) {
				arr[j] = 1;
				cnt++;
				if (cnt == k) {
					cout << j << endl;
					return 0;
				}
			}
		}
	}
}

 

제출 결과

(2022.05.03 백준 2960번 문제 제출 결과)