[백준] 2960. 에라토스테네스의 체

문제

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


풀이

일단 1000개 밖에 없으므로 각 index가 탐색이 되었는지 여부를 확인하는 배열을 만들어서 0으로 초기화 하고 탐색됐으면 1로 바꿔준다.
아이디어는, 가령 2를 먼저 선택했을 때, 2, 4, 6, 8 ... 즉 2의 배수는 전부 탐색완료 상태로 만들어주고 다시 처음으로 돌아가면 가장 작은 소수는 3이 될 것이다. 역시 3의 배수를 전부 탐색 완료로 바꿔주고 다시 처음으로 돌아가면 이미 4는 탐색완료 상태이므로 다음 수는 5가 될 것이다. 이런식으로 소수의 배수들을 전부 탐색 완료 상태로 바꿔줘가면 찾고자 하는 수를 찾을 수 있다. 이 때, 한번의 탐색에 cnt는 1씩 증가한다. (k번째를 지우는 것이므로)


소스코드

//
//  2960.cpp
//  test
//
//  Created by 신기열 on 27/06/2019.
//  Copyright © 2019 신기열. All rights reserved.
//
#include <stdio.h>
#include <iostream>

using namespace std;

int Sieve[1001] = { 0, };

int main(){
    
    int N, K, flag = 0, ans = 0, cnt = 0; cin >> N >> K;
    
    for(int i = 2; i <= N; i++){
        if(Sieve[i] == 0){
            cnt++;
            Sieve[i] = 1;
            
            int j = 1;
            if(flag == 1){ ans = i; break; }
            
            while(i * j <= N){
                
                if(Sieve[i * j] == 0){ Sieve[i * j] = 1; cnt++; }
                if(cnt == K){ ans = i * j; flag = 1; break; }
                j++;
            }
        }
        if(flag == 1) break;
    }
    
    cout << ans;
    return 0;
}

소스코드 : https://github.com/betterafter/BaekJoon/blob/master/Erato/2960.cpp