[수학] BOJ 2960 에라토스테네스의 체

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

2960번: 에라토스테네스의 체

 

- 문제 파악

2부터 입력에서 주어진 수만큼 배수를 지운다. 지운 배수들은 배열에 넣어놓고 반복문에서 이미 지운 배수를 조회할 땐 지나친다.

 

- 정답 코드

#include "bits/stdc++.h"

using namespace std;

int arr[1005];

int main()
{
    int n, k;
    cin >> n >> k;

    int ans = 0;

    for (int i = 2; i <= n; i++)
    {
        int j = 0;
        while (++j)
        {
            int a = i * j;
            if (a > n) break;
            if (arr[a]) continue;

            arr[a]++;
            ans++;

            if (ans == k)
            {
                cout << a;
                return 0;
            }
        }
    }

}