Boj 1978 c++ 소수 찾기

 

#include<iostream>

using namespace std;

int main() {
   int n, num, cnt=0, prime;
   cin>>n; 
    for(int i=0; i<n; i++) {
        prime=1;
     cin>>num;
       if(num<2){
        prime=0;}
     
  else
      for(int j=2; j*j<=num; j++){
          
          if(num%j==0){
              prime=0;
              break;}
     
       }
        
   if(prime==1)
       cnt++;
   
}
  cout<<cnt;
   
    
    


}

n개의 소수가 입력되었을 때 소수의 개수를 출력하는 알고리즘이다.

우선 2부터 sqrt(n)의 값 까지 루프를 돌려 약수가 존재하는지 판별한다. 약수가 하나라도 존재하면 소수가 아니기에 prime값에 0(false)를 입력한다. 만약 끝까지 나누어 떨어지는 수가 없으면 소수이기에 prime값은 1(true)가 된다. 참 거짓에 따라 cnt++를 하면 소수의 개수를 출력할 수 있다.