1978번: 소수 찾기 (백준 온라인 저지, C++)

문제 풀이

 

 에라토스테네스의 체를 활용하여 소수를 구했습니다.

(https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4)

 

 

코드

 

#include <iostream>
#include <vector>
 
using namespace std;
 
int d[1001] = { 0, };
 
int main() {
 
    int n;
    int m = 0;
    cin >> n;
 
    vector <int> v;    
    for (int i = 0; i < n; i++)
    {
        int x;
        cin >> x;
        if(x > m)
            m = x;
        v.push_back(x);
    }
    
    d[1] = 1;
    for (int i = 2; i <= m; i++)
    {
        if (d[i] == 0)
        {
            for (int j = i; j*i <= m; j++)
            {
                if (d[j*i] == 0)
                    d[j*i] = 1;
            }
        }
    }
 
    int ans = 0;
    for (int i = 0; i < n; i++)
    {
        if (d[v[i]] == 0)
            ans++;
    }
 
    cout << ans;
 
    return 0;
}

 

 

제출 결과

 

 

 

문제 출처

 

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

1978번: 소수 찾기