BOJ-1978 | 소수 찾기 c++

✏️ 1978 - 소수 찾기
🌊 GitHub @xaesu, Study-Algorithm

접근

✔️ 소수 판별

1. 소수 : 1과 자기 자신만을 약수로 갖는 수
   → 1은 소수가 아니다.

2. 반복문을 통해 2부터 자기 자신보다 작은 수 중 나누어 떨어지는 수가 없으면 소수
   → 입력 값이 클 경우 시간 초과 우려가 있으므로 제곱근까지만 반복 : sqrt()
   → sqrt() 함수 : <cmath> 헤더파일 사용 필요

3. 에라토스테네스의 체
   → 1~ 자기 자신 중에서 소수의 개수를 파악하는 데에 용이한 알고리즘 --- 그냥 반복문으로 접근함

풀이

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

bool isPrime(int num);

int main() {
    int N, cnt = 0;
    cin >> N;

    int * num = new int [N];

    // 입력
    for (int i = 0; i < N; i++) {
        cin >> num[i];
    }

    // 소수일 경우 갯수 추가
    for (int i = 0; i < N; i++) {
        if (isPrime(num[i])) cnt++;
    }

    cout << cnt;
}

// 소수 판별 (1은 소수가 아님)
bool isPrime(int num) {
    if (num > 1) {
        for (int i = 2; i <= sqrt(num); i++) {
            if (num % i == 0) return false;
        }
        return true;
    }
    else return 0;
}