[1978번] 소수 찾기

📌풀이

 

• 기본 접근 : 2부터 N-1까지의 수로 주어진 수를 나눔으로서 소수인지 아닌지 판별.
• 에라토스테네스의 접근 : 제곱근을 사용해 주어진 수가 소수인지 아닌지를 판별.
• 에로토스테네스의 체 : 2부터 제곱근N까지 나눔으로주어진 수까지의 모든 소수를 구함.

멋들어지게 에라토스테네스의 접근을 사용해보고자 했지만 때려치웠다. 기본 접근으로 풀었음.

 

참고 :

https://jongmin92.github.io/2017/11/05/Algorithm/Concept/prime/

소수 구하기 (에라토스테네스의 체)

 

📌코드

#include <stdio.h>
#include <math.h>

int main(){
    int count, prime=0, num;

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