1978번. 소수 찾기

문제

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

입력

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

출력

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

예제 입력

4

1 3 5 7

예제 출력

3

 

코드

#include <iostream>
using namespace std;

bool isPrimeInt(int num) {
    if(num <= 1) return false;
    for(int j = 2; j*j <= num; j++) {
        if(num%j == 0) {
            return false;
        }
    }
    return true;
}

int main() {
    int tc;
    int num;
    int cnt = 0;
    
    cin >> tc; // 테스트 케이스
    for(int i = 0; i < tc; i++) {
        cin >> num; // 테스트 데이터
        if(isPrimeInt(num)) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

j*j 를 적용한 이유는 검색을 해보았다.

입력받은 숫자의 제곱근 까지의 숫자로 나누기만 해도 답을 찾을 수 있다.

25라면 2, 3, 4, 5만으로도 나누어 떨어지니 소수가 아니고 41은 2, 3, 4, 5, 6으로 나누어 떨어지지 않으니 소수라고 할 수 있다.