1978번: 소수찾기(백준 C++)

소수 찾기

문제

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

입력

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

출력

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

예제 입/출력 1

입력

4
1 3 5 7

출력

3

---

이번에 네이버 블로그에서 티스토리로 전향했다.

 

어차피 네이버 블로그 해도 보러 오는 사람도 없었긴 했지만, 네이버 블로그에서는 마크다운 작성이 안 된다는걸 알아버렸기 때문이다..

 

쓴 지 얼마 안됐을 때 알아서 다행이다. 글 9개 옮기는 것도 이렇게 귀찮았는데 좀만 더 많았으면 그냥 네이버 했을지도 모르겠다. 근데 옮기는 것도 서식이 100% 옮겨지는 건 아니어서 영 보기가 그렇다.

 

지금부터라도 잘 써야지

코드

#include <iostream>
#include <cmath>
using namespace std;

bool judge_prime(int n){
    if(n == 1) return false;

    for(int i = 2; i < int(sqrt(n)) + 1; i++ )
        if(n % i == 0)    return false;

    return true;
}
int main(){
    int n;
    int cnt = 0;
    int arr[100];

    cin >> n;

    for(int i=0; i<n; i++)
        cin >> arr[i];

    for(int j=0; j<n; j++)
        cnt = judge_prime(arr[j]) ? cnt + 1 : cnt;

    cout << cnt;
}

사견

문제 자체가 그렇게 어려운 건 아니었다.
소수를 찾는 방법에는 대표적으로 '에라토스테네스의 체'가 있긴 하지만, 입력되는 숫자의 개수도 최대 100에 입력되는 수의 최대값이 1000밖에 되지않는다면 굳이 에라토스테네스의 체를 사용할 필요가 없다고 생각했다.

또한, 연속된 수의 범위였다면 에라토스테네스의 체가 효과적이었겠지만, 비연속적인 수의 나열에서 소수를 찾는다면
수 하나하나 소수의 자격을 판단하는 것이 옳다고 생각했다.

해서 2부터 주어진 수의 제곱근값 까지의 수로 주어진 수를 나누었을 때, 나누어진다면 소수가 아니라는 방법을 활용하여 소수 판별하는 함수를 작성하였고, 이를 활용하여 문제를 해결했다.