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

문제 설명

 

=> 에라토스테네스의 체를 사용할 줄 아는지 묻는 문제입니다.

=> 실제로 소수를 구하는 것이 아닌 지워지는 것을 구하는 것이기 때문에 소수이더라도 지워진다고 생각하면 편합니다. 

=> check 배열을 사용하여 문제를 해결할 수 있습니다. 

 

 

 

 

 

 

https://codingham.tistory.com/32

백준 2581 - 소수

=> 이전에 푼 문제와 거의 비슷한 문제입니다. 

 

 

 

 

 

 

 

 

 

<code>

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    
    bool check[1001]= {false};
    
    int N, K;
    cin >> N >> K;
    int pn =0;
    
    for(long i=2; i<=N; ++i)
    {
        if(check[i] == false)
        {
            for(long long j=i; j<=N; j+=i)
            {
                if(check[j] == false)
                {
                    check[j]=true;
                    K--;
                    if(K == 0)
                    {
                        cout<<j<<'\n';
                        return 0;
                    }
                }
                
            }
        }
    }
    return 0;
}

 

 

실행화면 1

 

실행화면 2