[백준] 1978번: 소수 찾기 - C++

문제

주어진 수 N개 중에서 소수가 몇 개인지 찾아서 출력하는 프로그램을 작성하시오.

 

입력

첫 줄에 수의 개수 N이 주어진다. N은 100이하이다. 다음으로 N개의 수가 주어지는데 수는 1,000 이하의 자연수이다.

 

출력

주어진 수들 중 소수의 개수를 출력한다.

---

소수를 찾는 알고리즘을 이용하여 풀 수 있는 문제.

소수는 1보다 큰 자연수 중 1과 자기 자신만을 약수로 갖는 자연수를 의미한다. 2, 3, 5, 7, 11 .. 등의 자연수가 소수로 속한다.

 

첫번째로 가장 기본적인 소수를 찾는 방법은 2부터 N까지의 수를 조사하는 방법이다. 2부터 N까지의 수 i로 N을 나눠보면서 나머지가 0이 나오는지 판별하는 것이다. 2부터 N까지 모든 경우의 수를 계산해보기 때문에 시간복잡도는 O(N)이 나온다.

bool isPrime(int N) {
    if(N <= 1) return false; // 1은 소수가 아님
    for(int i = 2; i < N; i++) {
    	if(i % N == 0) return false; // 하나라도 나눠떨어지는 수가 있을 경우 소수가 아님
    }
	return true;
}

 

두번째 방법은 2부터 √N까지의 수만 조사하는 방법이다. 첫번째 방법과 거의 동일한데, 범위만 달라진다.

36을 예로 들면, 36의 약수는 1, 2, 3, 4, 6, 9, 12, 18, 36이다. 여기서 √36 = 6 을 기준으로 1 * 36, 2 * 18, 3 * 12, 4 * 9 처럼 곱하는 수들이 대칭을 이루기 때문에 그 이상의 수를 검사하는 것은 의미가 없어 제곱근까지의 수만 검사하면 된다. 시간복잡도가 O(√N)으로 위의 경우보다 효율적인 편이다.

bool isPrime(int N) {
    if(N <= 1) return false; // 1은 소수가 아님
    for(int i = 2; i * i =< N; i++) {
    	if(i % N == 0) return false; // 하나라도 나눠떨어지는 수가 있을 경우 소수가 아님
    }
	return true;
}

제곱근의 처리가 번거롭기 때문에 i * i <= N과 같은 방법으로 범위를 지정해준다.

 

두번째 방법으로 풀이하였으나, 둘 중 어느 방법으로 풀어도 상관없다.

 

코드

#include <cstdio>
#include <vector>

using namespace std;

bool IsPrime(int num);

int main(void) {
    int n;
    scanf("%d", &n);
    
    int result = 0;
    for(int i = 0; i < n; i++) {
        int temp;
        scanf("%d", &temp);
        if(IsPrime(temp)) result++;
    }

    printf("%d\n", result);
    return 0;
}

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