소수 찾기

레벨: 브론즈 2
날짜: 2023년 4월 6일 오후 8:04
문제번호: 1978
알고리즘: 소수판정, 수학, 정수론

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	128 MB	163149	76270	60936	46.613%

문제

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

입력

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

출력

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

예제 입력 1

4
1 3 5 7

예제 출력 1

3

풀이

#include <iostream>

using namespace std;

int main() {
    
    int n;
    int cnt=0; //소수 카운트
    cin>>n;
    int max = 0;
    int arr[n];
    for(int i=0; i<n;i++) {
        cin>>arr[i];
        if(max<arr[i])
            max = arr[i];
    }

    // 나누어 줄 수(소수인 2부터 n개중의 max값까지)
    for(int i=1; i<=max; i++) {
        //1은 건너뛰어야하지만 max가 1일수도있으니 for문 안에서 스킵해주었다.
        if(i==1)
            continue;
        //배열을 전부 스캔하면서 에라토스테네스의 체 원리를 적용한다.
        for(int j=0; j<n; j++) {
            //1은 소수가 아니니 제거
            if(arr[j]==1){
                arr[j]=-1;
                continue;
            }
            //제거된 값들은 스킵
            if(arr[j]==-1){
                continue;
            }
            //제일 처음 선택된 값 또한 제거하면 안되므로 스킵(ex.2,3,5,7)
            if(arr[j]==i) {
                continue;
            }

            if(arr[j]%i==0){
                arr[j]=-1;
            }
        }
    }

    //소수 카운트
    for(int i=0; i<n; i++) {
        if(arr[i]!= -1)
            cnt++;
    }

    cout<<cnt<<endl;

    return 0;
}