[백준 BOJ] 1929번 소수 구하기 (C++/cpp)

문제 설명

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

1929번: 소수 구하기

 

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

백준의 1929번 문제는 에라토스테네스의 체를 응용하여 해결해야 하는 기본 문제이다.

해당 문제는, 특정 범위 내의 소수를 오름차순으로 출력해야 하는 문제이다.

여기서, 소수는 특정 숫자의 약수가 1과 자기 자신뿐인 숫자를 뜻한다.

이러한 소수를 구하는 데에 많이 쓰이는 알고리즘이 바로 에라토스테네스의 체이다.

이 개념에 대해 아직 어색하다면, 아래 필자의 설명을 참고하거나 구글링을 해보길 권한다.

(여기서, 필자는 에라토스테네스의 개념만 알고 구현하였기 때문에 정석적인 코드는 아닐 수 있다. 이 점 유의하길 바란다.)

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

 

코드의 실행 순서

1) 문제에 제시된 입력값의 최대 범위만큼의 크기를 가진 배열(arr)을 전역 변수로 선언한다.

 

2) arr를 통해 에라토스테네스의 체를 실행하고자 한다. 필자는 아래의 규칙을 가지고 이를 실행하였다.

(arr의 배열값이 0인 경우는 소수이며, arr의 배열값이 1인 경우는 소수가 아니다.)

- 숫자 0과 1은 소수가 아니기 때문에, 이 두 숫자는 우선적으로 소수에서 배제시키도록 한다. 따라서, arr[0]와 arr[1]의 값을 1로 설정한다.

- 반복문 하나를 실행한다. (여기서, 제어 변수 i는 2에서부터 시작한다.)

- 다른 제어 변수 k 또한 2에서부터 시작하도록 한다.

- 다른 반복문을 작성한다. 이 반복문은 숫자 i가 소수로 판별되었을 경우에만 실행하도록 한다.

여기서 i*k의 값이 입력값 최대 범위 밖으로 넘어가지 않는다면, arr[i*k]의 값에 1을 더하면서 k의 값을 1 증가시킨다.

(소수는 1과 자기 자신만을 약수로 가진다. 따라서, 1과 자기 자신을 제외한 다른 숫자의 배수가 될 수 없음을 이용한 것이다.)

 

3) 소수 판별이 모두 끝났다면, 특정 범위(a, b)를 입력받는다.

 

4) 반복문으로 범위 안의 값들을 탐색한다.

만일 현재 탐색한 arr의 배열값이 0이라면, 이는 소수이다. 따라서 이 경우엔 해당 숫자를 출력하도록 한다.

 

5) 출력이 모두 끝났다면, 실행 종료한다.

반응형

 

성공한 코드

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

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

	arr[0] = 1;	arr[1] = 1;
	for (int i = 2; i <= 1000000; i++) {
		int k = 2;
		while (arr[i] == 0) {
			if (i * k > 1000000) { break; }
			arr[i * k]++;
			k++;
		}
	}

	int a, b;
	cin >> a >> b;
	for (int i = a; i <= b; i++) {
		if (arr[i] == 0) { cout << i << endl; }
	}
}

 

제출 결과

(2022.05.08 백준 1929번 문제 제출 결과)