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

문제 링크 : https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

문제 풀이

만일 N이 2부터 √n의 수까지 나누어 떨어지는 경우가 있으면 이는 소수가 아니다.

이를 활용하여 풀이하였다.

#include <iostream>

using namespace std;

int A[102];
int n, cnt;

int main() {
    ios::sync_with_stdio(0);  
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 0; i < n; i++) cin >> A[i];
    for(int i = 0; i < n; i++){
        if(A[i] == 1) continue;
        if(A[i] == 2 or A[i] == 3){
            cnt++;
            continue;
        }
        bool flag = true;
        for(int j = 2; j*j <= A[i]; j++){
            if(A[i]%j == 0){
                flag = false;
                break;
            }
        }
        if(flag) cnt++;
    }
    cout << cnt;
}