[C/C++] 백준 2960번 : 에라토스테네스의 체

1. 문제

 

에라토스테네스의 체에 관한 문제이다. 관련 알고리즘 로직을 알고 응용해서 푸는 문제이다.

 

2. 에라스토스테네스의 체란?

참고 : https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

에라토스테네스의 체 - 위키백과, 우리 모두의 백과사전

 

에라토스테네스의 체란, 소수를 빠르게 찾는 알고리즘 중 하나이다. 특정 범위 내에서 소수를 판별할 때 효과적으로 쓰인다. 배수를 제거하는 방식으로 동작하며, 시간 복잡도가 매우 빠르다 (O(NloglogN)).

 

How?

1) 2부터 N까지의 모든 정수를 배열에 저장

2) 초기값은 모두 TRUE (모든 수를 소수로 봄)

3) 2부터 차례대로 소수에 대한 배수를 FALSE로 지정

4) 남아있는 수는 모두 소수

 

3. 풀이

에라토스테네스의 체는 소수를 찾는 방식이지만, 문제에서는 소수를 포함한 K번째 지워진 수를 찾아야하기 때문에 소수도 지우고 N까지 완전 탐색해야 한다.

 

1) T/F 값을 지정할 모든 정수를 가진 배열 선언

2) 배열을 전부 TRUE로 초기화(모든 값을 소수로 봄)

3) 소수와 그 배수를 지울 때마다 Count

4) 만약 cnt가 k값과 같다면(k번째 값이 지워졌다면), k번째 지워진 값을 출력하고 빠져나옴

 

 

4. 코드

 

제출한 코드 (C)

 

2부터 N까지의 수를 저장해야하기 때문에 배열의 크기를 N+1로 지정하고 T/F 값을 지정하기 위해 타입을 Boolean으로 설정했다. 초기값은 모두 TRUE로 설정하고 cnt 변수를 선언하여 소수를 포함한 배수가 지워질 경우 cnt를 증가시켰다. cnt 값이 K와 같을 경우 수를 출력하고 빠져나오도록 했다.

#include <stdio.h>
#include <stdbool.h>

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    bool arr[n+1];
    for(int i=2; i<=n; i++){
        arr[i] = true;
    }

    int cnt=0;
    for(int i=2; i<=n; i++){
        if(arr[i]){
            arr[i]=false;
            cnt++;

            if(cnt==k){
                printf("%d", i);
                return 0;
            }
            
            for(int j=i*i; j<=n; j+=i){

                if(arr[j]){
                    arr[j]=false;
                    cnt++;
                }
                
                if(cnt==k){
                    printf("%d", j);
                    return 0;
                }
            }
        }
    }

    return 0;
}

 

하지만 이 코드에는 문제점이 많았다. 특히 불필요하게 로직을 반복하여 보기에 좋지 않았다. 

 

개선된 코드 (C)

 

#include <stdio.h>
#include <stdbool.h>

int main() {
    int n, k;
    scanf("%d %d", &n, &k);

    bool arr[n+1];
    
    // 개선 1 : 안쓰는 자리는 false로 둠
    arr[0] = arr[1] = false;
    for (int i = 2; i <= n; i++) {
        arr[i] = true;
    }

    int cnt = 0;

    for (int i = 2; i <= n; i++) {
        if (arr[i]) {  
        	// 개선 2 : 소수도 함께 지우기 위해 j값을 i*i가 아닌 i로 지정
            for (int j = i; j <= n; j += i) {
                if (arr[j]) {  
                    arr[j] = false;
                    cnt++;
					
                    // 개선 3 : 개선 2와 함께 반복되는 로직을 줄임
                    if (cnt == k) {
                        printf("%d\n", j);
                        return 0;
                    }
                }
            }
        }
    }

    return 0;
}

 

반복되는 로직을 줄이고, 안쓰는 배열의 0과 1 자리는 명시적으로 false로 지정해주었다. 

 

C++ 코드

 

#include <iostream>
#include <vector>

using namespace std;

int main() {

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

    vector<bool> arr(n + 1, true);
    arr[0] = arr[1] = false;

    int cnt = 0;
    for (int i = 2; i <= n; i++) {
        if (arr[i]) {
            for (int j = i; j <= n; j += i) {
                if (arr[j]) {
                    arr[j] = false;
                    cnt++;

                    if (cnt == k) {
                        cout << j;
                        return 0;
                    }
                }
            }
        }
    }

    return 0;
}

 

vector<bool> 을 사용하여 배열을 선언하고, 나머지 로직은 그대로다.

 

 

감사합니다 (｡･∀･)ﾉﾞ