[백준] 1978번 소수 찾기 C++ 문제 풀이 수학 2

문제

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

입력

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

출력

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

---

예제 입력 1

4

1 3 5 7

---

예제 출력 1

3

---

문제 풀이

#include <iostream>
#include <cmath>

using namespace std;

int main() {
  int N, num, cnt = 0, max;
  cin>>N;
  for(int i=0; i<N; i++){
    cin>>num;
    max = sqrt(num);
    if(max == 1 && num != 1){
      cnt++;
      continue;
  }
    if(num%2 == 0)
      continue;    
    for(int j=2; j<=max; j++){
      if(num%j == 0)
        break;
      if(j == (int)max)
        cnt++;      
    }
  }
  cout<<cnt<<'\n';
}

이 코드는 num을 입력 받고 2부터 num의 제곱근 까지 검사하여 num이 0으로 나누어 떨어지는 수가 없을 경우 소수로 판단하는 코드입니다.

 

제곱근이 1인 수는 1, 2, 3이고 그 중에 2, 3이므로 먼저 따로 빼주었습니다.

if(max == 1 && num != 1){
      cnt++;
      continue;
  }

 

num이 2로 나누어 떨어질 경우 짝수 이므로 소수가 될 수 없습니다.

if(num%2 == 0)
      continue;  

 

for 문에서는 2부터 num의 제곱근까지 num이 0으로 나누어 떨어지는 지 검사합니다.

0으로 나누어 떨어질 경우 소수의 조건을 만족시킬 수 없으므로 break문으로 종료하고,

반복이 num의 제곱근 까지 이루어졌다면 소수이므로 cnt값을 증가시켜 줍니다.

for(int j=2; j<=max; j++){
      if(num%j == 0)
        break;
      if(j == (int)max)
        cnt++;      
}

 

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

1978번: 소수 찾기