1978번 소수 찾기 문제를 풀어보았다.

1978 소수찾기

 

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

1978번: 소수 찾기

 

소수 찾기 문제이다.

이 문제의 경우는 간단한 문제지만, 숫자 하나하나를 전부 일일히 소수인지 판단해서는 시간초과가 나버릴 것이라고 판단했다.

그래서 [에라토스테네스의 체] 알고리즘을 사용하였다.

이 알고리즘은 간단한 원리이다.

i+i번째부터 i만큼씩 커져가는 모든 부분은 소수가 아니게된다.

즉 i=2일때, 4,6,8,10,12... 수들은 소수가 아니라고 체크를 하고,

i=3일때, 6,9,12,15,18... 수들은 소수가 아니라고 체크를 하는 것인데,

지금 이것만 봐도 겹치는 부분이 생긴다는 것을 알 수 있다.

굳이 체크한 부분을 다시 체크할 필요가 없다. 따라서 i가 이미 체크가 되어있을 때는 넘어가게 하였다.

그리고 소수는 n의 배수가 아니어야 하므로, 입력 범위인 1000보다 작은 수들로 나누어서 떨어지면 소수가 아니게 된다.

따라서 루트 n 까지만 나누어 떨어지면 소수가 아닌 것이다.

그렇게 소수인 수들을 먼저 확인해두고, 입력을 받아서 그 수가 소수라면 카운트하였다.

 

#include <stdio.h>
#include <math.h>
int main()
{
    int t,n,i,j,cnt=0;
    int arr[1001]={0};
    for(i=2;i<1001;i++) arr[i]=i;
    for(i=2;i<=sqrt(1000);i++) {
        if(!arr[i]) continue;
        for(j=i+i;j<=1000;j+=i) {
            arr[j]=0;
        }
    }
    scanf("%d",&t);
    for(i=0; i<t; i++) {
        scanf("%d",&n);
        if(arr[n]) cnt++;
    }
    printf("%d",cnt);
}