BOJ 1978 · 소수 찾기

알고리즘 분류 : 수학  

소수(Prime number)란 1과 자기 자신의 숫자로만 나누어떨어지는 2 이상의 자연수를 말한다. 예를 들면 2는 1과 2로만 나눌 수 있으며, 5는 1과 5로만 나눌 수 있다. 6은 1, 2, 3, 6으로 나눌 수 있으므로, 소수가 아니다.

• 2 미만의 정수는 소수가 아니다.
• 숫자 N이 소수인지 아닌지를 판별하기 위해서 2부터 N-1까지 나눠보면 된다. 한 번이라도 나누어떨어지는 수가 존재하면, 그 수는 소수가 아니다.
• N-1까지 확인하면 속도가 느리다. 루트 N까지만 확인해도 소수인지 아닌지 판별할 수 있다.

---

C++ 소스코드

#include <cstdio>

bool prime(int x) {
    if (x < 2) return false;
    for (int i=2; i*i<=x; i++) {
        if (x%i == 0) return false;
    }
    return true;
}

int main() {
    int n;
    scanf("%d", &n);
    int cnt = 0;
    while (n--) {
        int x;
        scanf("%d", &x);
        if (prime(x)) cnt++;
    }
    printf("%d\n", cnt);
    return 0;
}

---

Python 3 소스코드

def prime(n):
    if n < 2:
        return False
    for i in range(2, n):
        if i*i > n:
            break
        if n % i == 0:
            return False
    return True


input()
a = list(map(int, input().split()))
cnt = 0
for x in a:
    if prime(x) is True:
        cnt += 1
print(cnt)

---

참고

• 백준 온라인 저지 : BOJ 1978
• 위키피디아 : 소수