[백준 / BOJ] - 1978번 소수 찾기 C++ 풀이

---

 

백준 - 단계별로 풀어보기 [1978] 

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

문제

 

 

1000이하의 자연수를 최대 100개 입력받은 후, 입력 받은 수 중 소수의 개수를 구하는 프로그램을 작성하는 문제이다.

 

풀이

 

우선 1000이하의 소수를 모두 구하는 것은 비효율적이므로, 각각의 숫자가 소수인지 아닌지를 판별하는것이 관건인 문제이다.

일반적인 접근 방법은 2보다 크고, 입력받은 수보다 작은 수까지를 모두 나눠보았을 때, 나눠지지 않으면 소수라고 판별하는 것이지만 보다 효율적이고 빠른 계산을 위해 에라토스테네스의 접근 방법을 사용한다.

 

에라토스테네스의 소수 필요충분조건은 2보다 크면서 자기 자신의 제곱근까지의 수에 나눠지지 않는 수이다.

즉 입력값의 재곱근까지 반복문을 돌려 소수 판별을 진행한다.

 

 

코드

 

#include <iostream>
#include <cmath>
using namespace std;
int main() {
    int num;
    cin >> num;
    int count = num;
    int input[100] = {0,};
    for(int i = 0; i < num; i++) {
        cin >> input[i];
        if (input[i] == 1)
            count--;
    }

    for(int i = 0; i < num; i++)
        for(int j = 2; j <= sqrt(input[i]); j++)
        {
            if(input[i] % j == 0)
            {
                count--;
                break;
            }
        }
    cout << count;
    return 0;
}

 

평가

 

난이도가 아주 쉬운 문제지만, 에라토스테네스의 접근 방법을 사용하면 보다 빠르게 풀 수 있는 문제이다.