백준 1978 번 문제 풀이 C C언어 :소수 찾기

#64. 백준 1978번 문제 풀이: 소수 찾기

주어진 수 N개 중 소수가 몇 개인지 출력하는 프로그램을 작성하시오. 입력: 첫 줄에 수의 개수 N. N은 100이하, 둘째 줄에 N개의 수. 수는 1,000 이하. 출력: 주어진 수들 중 소수의 개수를 출력.

입력/출력

--입력--
4
1 3 5 7
--출력--
3

문제풀이+해설

소수는 1과 자기자신으로만 나누어지는 1보다 큰 정수이다.
예) 2, 3, 5, 7, ..

소수를 판단하는 루틴은 다음과 같이 구현할 수 있다.
--
주어진 수를 n이라 하자. 
루프 ( i=2 부터 n-1 까지):
 만약 n%i 나누어 떨어지면 소수가 아니다. 빠져나옴
루프 끝
--

code sol.

코드편집/실행

#include <stdio.h>

int main() {
  int i, j, N, n, count, so;
  
  scanf("%d", &N); // 숫자 개수를 입력받아 정수형으로 대입
  count = 0; // 소수 개수 카운트
  for(i = 0; i < N; i++) { // 개수만큼 반복
    scanf("%d", &n); // 공백으로 구분된 숫자를 하나씩 받아드림
    so = 1; // 소수확인용 변수
    if(n == 1) so = 0; // 1은 소수가 아니므로 별도 처리.
    for(j = 2; j < n; j++) { // 2부터 n-1까지 i로 전달하고 루프
      if(n % j == 0) { // 다른 수로 나누어 떨어지면 소수가 아님
        so = 0; // 소수가 아님
        break; // 소수가 아니므로 확인 중지
      }
    }
    if(so == 1) count++; // 소수이면 count 증가 
  }    
  printf("%d", count); // 소수 개수 출력
  return 0;
}