[백준/C언어] 1978번 - 소수 찾기

백준 웹사이트 "1978번 - 소수 찾기" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

1978번: 소수 찾기

---

소스 코드

#include <stdio.h>
 
int main(void){
    int N;
    scanf("%d", &N);
 
    int numbers[N];
    for(int n=0; n<N; n++){
        scanf("%d", &numbers[n]);
    }
 
    int count=0;
    for(int i=0; i<N; i++){
        int number = numbers[i];
 
        // number이 소수인지 확인, 소수라면 count++
        for(int j=2; j<number; j++){ // 2는 고려하지 못함
            if(number%j==0){
                break;
            }
            if(j==number-1){
                count++;
            }
        }
        if(number==2)
            count++;
    }
    printf("%d\n", count);
}

---

문제 풀이

  주어진 수들 중에서 어떤 수들이 소수인지 판별하여, 총 소수의 개수를 구하는 문제입니다. '단계별로 풀어보기 9단계 - 기본 수학 2' 내에 소수를 구해야하는 문제들이 여럿 있는데, 그중 가장 기본적인 문제입니다.

  소수는 1과 자기 자신만을 약수로 가집니다. 즉, 2부터 (소수 - 1)까지의 숫자들로 모두 주어진 수를 나누어보고, 그 어떤 숫자로도 나누어떨어지지 않는다면, 주어진 수는 소수가 됩니다. Line 17 ~ 26은 이러한 원리를 이용하여 주어진 숫자가 소수인가를 판별합니다. 한 가지 주의할 점은 Line 17의 for문은 주어진 수가 2일 경우를 고려하지 못합니다. 하지만 2 역시도 소수이기 때문에, Line 25와 같이 따로 고려해야 합니다.

  만약 N이 매우 크거나 주어지는 수들이 매우 크면 시간 초과가 일어날 가능성이 있습니다. 이럴 경우, 소수들을 미리 한 번에 구해놓는 방법도 있습니다. 하지만 이 문제의 경우, N도 100 이하이고 주어지는 수들도 1000 이하이기에 시간 초과가 일어나지 않습니다. 소수들을 미리 구해놓는 방법은, 추후의 문제에서 다루겠습니다.