[백준/C++] 1978번 : 소수 찾기

문제

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

입력

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

출력

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

풀이

여기에서 말하는 소수는 Prime Number이다.

01. 1은 소수가 아니다.

02. 2부터 제곱근까지 반복문을 돌리며 배수 여부를 판별한다.

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

int main(){
    int N, num, cnt=0;
    cin >> N;
    bool isPrime = true;
    for (int i = 0; i<N; i++){
        cin >> num;
        if (num == 1){ // 1은 소수가 아님
          isPrime = false;
        }
        else {
          for (int j=2; j<=sqrt(num); j++){ // 제곱근까지 배수 돌리기
            if (num%j==0){
                isPrime = false;
                break;
            }
          }
        }
        if (isPrime == true)
            cnt += 1;
        isPrime = true;
    }
    cout << cnt << endl;
}