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

문제

에라토스테네스의 체는 N보다 작거나 같은 모든 소수를 찾는 유명한 알고리즘이다.

이 알고리즘은 다음과 같다.

1. 2부터 N까지 모든 정수를 적는다.
2. 아직 지우지 않은 수 중 가장 작은 수를 찾는다. 이것을 P라고 하자.
3. P를 지우고, 아직 지우지 않은 P의 배수를 크기 순서대로 지운다.
4. 아직 모든 수를 지우지 않았다면, 다시 2번 단계로 간다.

N과 K가 주어졌을 때, K번째 지우는 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ K < N ≤ 1000)

예제 입력 1

7 3

예제 입력 2

15 12

예제 입력 3

10 7

출력

첫째 줄에 K번째 지워진 수를 출력한다.

예제 출력 1

6

예제 출력 2

7

예제 출력 3

9

풀이

문제 해결 방법

이 문제는 에라토스테네스의 체 알고리즘을 구현하되, 수를 지우는 순서를 기록해야 합니다. 주요 해결 단계는 다음과 같습니다:

1. 배열 초기화: 2부터 N까지의 수를 배열에 표시합니다.
2. 최소값 찾기: 지우지 않은 수 중 가장 작은 수를 찾습니다.
3. 수 지우기: 찾은 수와 그 배수들을 순서대로 지우면서 카운트합니다.
4. K번째 수 찾기: K번째로 지워지는 수를 출력합니다.

이 알고리즘의 시간 복잡도는 O(N log log N)입니다.

코드

#include<stdio.h>

int n,k,cnt;
int data[1001];

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

    for(i=2;i<=n;i++)
    {
        if(data[i]==0)
        {
            cnt++;
            if(cnt==k)
            {
                printf("%d",i);
                return 0;
            }
            for(j=i*i;j<=n;j+=i)
            {
                if(data[j]==0)
                {
                    cnt++;
                    if(cnt==k)
                    {
                        printf("%d",j);
                        return 0;
                    }
                    data[j]=1;
                }
            }
        }
    }
    return 0;
}

소수 구하기

#include<stdio.h>

int n, k;
int p[1001];

int main()
{
    int i, j;
    scanf("%d%d", &n, &k);
    // n이 소수인지 판별하기 위해서는 root n까지만 보면 된다.
    for (i = 2; i * i <= n; i++)
    {
        if (p[i] == 0)
        {
            for (j = i * i; j <= n; j += i)
            {
                p[j] = 1;
            }
        }
    }

    vector<int> prime;
    for (i = 2; i <= n; i++)
    {
        if (p[i] == 0)prime.push_back(i);
    }
    return 0;
}