백준 - 2960 에라토스테네스의 체

문제 링크

소수와 관련된 다른 문제를 풀기위해 자세히 알아보게된 에라토스테네스의 체이다. 에라토스테네스의 체란 빠르게 소수들을 구하는 방법이다. 즉 특정수 n 이하의 모든 소수를 구하고 싶으면, n이하의 수중 합성수들을 지워나가면, 남은 숫자들은 소수가 된다는 것에서 착안한다.

먼저 2 이상의 가장 작은 수중, 아직 지우지 않는 수를 찾는다.  아직 하나도 지우지 않았으므로 2를 선택한다. 2는 소수이다, 그럼 2의 배수들은 전부 합성수들이므로, 2의 배수들은 모두 지워나간다.

그다음에 지워지지 않은 가장 작은 수는 3이다. 3은 소수이고, 3의 배수들은 전부 합성수이므로 3의 배수는 전부 지워나간다. 숫자를 다 지울때까지 반복한다.

이게 바로 에라토스테네스의 체이다. 

빠른 이해를 위한 이미지. 출처 위키피디아

이 문제는 에라토스테네스의 체처럼 소수를 구하는 문제와는 거리가 멀고, 에라토스테네스의 체가 어떤 순서로 숫자들을 지워나가고, 원하는 순서의 숫자를 구하는 문제이다. 그냥 이는 에라토스테네스의 체를 구현한 다음 해당 번째에서 출력하고 종료하면 되는 문제였다.

밑은 해당 소스코드이다.

#include <cstdio>
int n,k,a[1001]={0,},i,count=0;
int main(){
    scanf("%d %d",&n,&k);
    while(count!=k){
        //지우지 않은 가장 작은 수를 찾는다. 
        for(i=2;i<=n;i++)
            if(a[i]==0) break;
        //다 찾았는데 i가 1000이라면 다 지웠으므로 탈출한다. 
        if(i==1000) break;
        //i번째 수를 1을 채워 지웠음을 표시하고, 차례로 그 배수를 지워나간다. 
        for(int j=1;j*i<=n;j++){
            //만약 지우지 않은 숫자이면 해당 숫자 카운트를 증가시킨다. 
            if(a[i*j]==0){
                a[i*j]=1;
                count++;
            }
            if(count==k){
                printf("%d",i*j);
                return 0;   
            }
        }
    }
}