백준 1978번[C] - 상세 풀이

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

1978번: 소수 찾기

---

1. 

#include <stdio.h>

int main() {
    int N, cnt = 0;
    
    int arr[100] = {0,};
    int check[1000] = {0, };
    scanf("%d", &N);
    for(int i = 0; i < N; i++) {
        scanf("%d", &arr[i]);
    }
    //에라토스테네스의 체 알고리즘
    for(int i = 2; i < 1000; i++) {
        if(check[i] == 0) {
            for(int j = i*i; j < 1000; j+=i) {
                check[j] = 1;
            }
        }
       
    }
    //소수의 개수 카운트
    for(int i = 0; i < N; i++) {
        if(check[arr[i]] == 0 && arr[i] != 0 && arr[i] != 1) {
            cnt++;
        }
    }
    printf("%d", cnt);
 
    return 0;
}

풀이 : 이 코드는 에라토스테네스의 체 알고리즘을 사용한 코드입니다.  문제에서 제시된 수의 범위는 1000이하의 자연수입니다. 따라서 2~1000까지 반복문을 돌며 소수는 0으로 지정, 소수의 배수들은 1로 바꾸며 소수판별을 끝냈습니다.
그 다음에는 입력된 값을 기준으로 소수인지 판단합니다. (check[arr[i]] == 0), 그리고 0과 1 또한 소수가 아니므로 조건을 추가시켰습니다. 

---

2.

#include <stdio.h>

int main() {

    int N, cnt = 0;
    int num;
    scanf("%d", &N);
    
    for(int i = 0; i < N; i++) {

        scanf("%d", &num);
        for(int j = 2; j<= num; j++) {
             if(j == num) {
                cnt++;
            }
            if(num % j == 0) {
                break;
            }
           
        }
    }
    printf("%d", cnt);
    return 0;
}

풀이 : 소수 판별을 값을 입력받았을 때 진행하는 방식입니다. 2부터 입력받은 num까지 반복문을 돌며 만약 나누지는 수(약수)가 있다면 소수가 아니라는 의미이고, j가 num이 되었을 때까지 약수가 없다는 건 소수이므로 그 때 카운트를 증가시킵니다. 따라서 cnt를 출력하면 소수의 개수를 구할 수 있습니다.