[백준 / C++] 1978. 소수 찾기

https://www.acmicpc.net/problem/1978

1978번: 소수 찾기

 

 

 

---

 

자신을 제외한 약수가 없는 수가 소수이므로 2부터 n/2(자기자신/2)까지만 확인하면 된다. 

소수는 1보다 큰 자연수여야 한다. (자기자신/2)보다 큰수는 약수가 될 수 없으므로 i를 2부터 last까지 1씩 증가시키며 반복한다.

n을 i로 나누었을때 나머지가 0이면(즉, i는 n의 약수가 아님), 소수가 아니므로 0을 반환한다. (i가 약수이므로 n은 소수가 아님)

1~last(자기자신/2)사이에 약수가 없으므로 소수이다.

 

 

---

제출 답안

#include <iostream>
using namespace std;

int isSosu(int n){
    int last = n / 2;
    
    if (n <= 1) return 0;

    for(int i = 2; i <= last; i++){
        if((n % i) == 0){
            return 0;
        }
    }
    return 1;
}

int main(void){
    int N, sosu, count = 0;
    cin>> N;

    for(int i = 0; i < N; i++){
        cin>> sosu;

        if(isSosu(sosu)){
            count++;
        }
    }
    cout<< count;
}