[C++] 백준 1978번 : 소수 찾기 (S4)

#문제

www.acmicpc.net/problem/1978

1978번: 소수 찾기

#풀이 & 학습한 내용

어떤 수 N이 소수인지 판정하기 위해 2부터 N-1까지의 수에 대해 N이 나누어 떨어지는지 살펴본다. 만약, 하나라도 나누어 떨어지는 수가 있다면 N은 소수가 아니다. 이때, 2부터 루트 N까지의 수에 대해서만 관찰해도 됨을 기억하자.

즉, 아래 소스코드의 15행은 for (int i=2; i*i<=n; i++)로 바꿀 수 있다.

#소스코드

#include<iostream>
#include<algorithm>
 
using namespace std;
 
int main(void) {
    int N;
    cin >> N;
 
    int sum = 0;
    int num;
    while (N--) {
        cin >> num;
        bool isit = true;
        for (int i = 2; i < num; i++) {
            if (num%i == 0) {
                isit = false;
                break;
            }
        }
        if (num == 1)
            isit = false;
        if (isit == true)
            sum++;
    }
    
    cout << sum << '\n';
}