[C/C++] 백준 #1978 소수 찾기(수학)

이번 문제는 N개의 수중에 소수인 수의 갯수를 찾는 것입니다.

 

Finding prime numbers

 

소수의 범위가 크지 않기 때문에 사실 미리 소수를 구해도 되고, 에라토스테네스의 체를 이용해도 됩니다.  소수의 범위 K(이 문제에서는 1,000)라고 한다면, 에라토스테네스의 체를 사용하면 \(O(K \sqrt{K})\)의 시간안에 소수를 찾을 수가 있습니다.  또한 이것 자체가 소수인지 아닌지 판별하는 배열이 되기 때문에 소수의 개수를 구하는 것도 \(O(N)\) 시간안에 찾을 수 있습니다.

 

저는 에라토스테네스의 체가 아니라, 주어진 수마다 소수인지 판별을 했습니다.  이 경우 \(O(N \sqrt{K})\) 시간안에 찾을 수가 있습니다.  알고리즘 효율로 본다면, \(N << K\)아므로 이 방법이 더 좋다고 볼 수 있습니다.

 

숫자의 범위가 크다면, 다른 접근 방법이 필요합니다.  밀러-라빈 소수 판정법을 비롯해서 다수의 소수 판정법이 있습니다.  그리고 큰 정수 자료구조를 사용해야 할 수도 있습니다.  큰 정수가 아니라면, \( O(\sqrt{N}) \) 알고리즘을 사용해도 충분합니다.

 

짝수 소수는 2 하나이므로 홀수에 대해서만 검사를 하도록 했습니다.

 

제가 작성한 소스입니다.

//------------------------------------------------
//    baekjoon #1978
//        - by Aubrey Choi
//        - created at 2019-05-31
//------------------------------------------------
#include <stdio.h>
#include <memory.h>

bool isprime(int p)
{
    if(p < 2) return false;
    if(p == 2) return true;
    if(p % 2 == 0) return false;
    for(int s = 3; s*s <= p; s += 2)
        if(p%s == 0) return false;
    return true;
}

int main()
{
    int n, count = 0, p;
    scanf("%d", &n);
    for(int i = 0; i < n; i++)
    {
        scanf("%d", &p);
        if(isprime(p)) count++;
    }
    printf("%d\n", count);
}