[BOJ1978][C++] 소수 찾기

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

 

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

 

 

출력

주어진 수들 중 소수의 개수를 출력한다.

 

 

예제 입력 1

4  1 3 5 7

 

예제 출력 1

3

 

 

출처

· 데이터를 추가한 사람: bclim9108

· 문제의 오타를 찾은 사람: djm03178

 

 

알고리즘 분류

· 수학

· 에라토스테네스의 체

 

 

코드

 

#include <iostream>
using namespace std;
 
int CheckPrimeNumber(int num);
 
int main()
{
    int n, num = 0, res;
    int ary[101];
    
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        cin >> ary[i];
    }
    
    for(int i = 0; i < n; i++) {
        res = CheckPrimeNumber(ary[i]);                                                                                          
        if (res == 2) num++;
        else continue;
    }
    
    cout << num << endl;
    
    return 0;
}
 
int CheckPrimeNumber(int a) 
{
    int cnt = 0;
    for (int i = 1; i <= a; i++) {
        if (a % i == 0) cnt++;
    }
    
    return cnt;
}

---

- 에라토스테네스의 체(Eratosthenes' sieve) : 그리스의 수학자이자 지리학자인 에라토스테네스가 고안한 소수(素數)를 찾는 방법으로, 이 방법으로 소수를 찾으려면, 2부터 시작해 자연수를 차례로 쓴 다음, 2 이외의 2의 배수, 3 이외의 3의 배수, 5 이외의 5의 배수의 순서로 수를 지워나가 끝에 남는 수가 소수이다.

[네이버 지식백과] 에라토스테네스의 체 [Eratosthenes' sieve] (두산백과)

소수(Prime Number)란, 숫자 1을 제외한 자기 자신의 수와 1로만 나누어지는 수를 의미한다.

for문을 이용하여 1부터 입력한 수까지 나누어 떨어질 경우 변수(cnt)의 크기를 하나씩 증가시켰다. 그리고 변수(cnt)의 크기가 2일 경우(1과 자기 자신의 수로만 나누어질 경우) 소수의 개수(num)를 증가시켰고, 최종적으로 num의 변수에 담긴 숫자를 출력하도록 하였다.