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

 

1978번: 소수 찾기

문제

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

 

 

입력

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

 

 

출력

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

 

 

예제 입력 1

4
1 3 5 7

예제 출력 1

3

 

 

해결 아이디어

소수 (수론) - 위키백과, 우리 모두의 백과사전

소수란, 1보다 큰 자연수 중 1과 자기 자신만을 약수로 가지는 수다. (1은 소수로 고려하지 않는다.)

첫번째 방법

단순히 반복문을 통해 입력된 숫자(num)를 2부터 num까지 반복하여 num % i == 0이 되는것을 검사할 수 있지만, 이 방법은 시간 복잡도가 O(n)으로 시간초과가 나올 가능성이 있기에, 조금 더 효율적인 방법으로 검사를 한다.

 

두번째 방법

2부터 입력된 숫자(num)의 반까지 (num / 2) 또는 (num * 0.5f) 반복하여 num % i == 0이 되는것을 검사하는 방법이다. 첫번째 방법보다 검사하는 횟수가 반 줄어서 비교적 효율적이지만 여전히 시간 복잡도가 O(n)으로 나타난다.

 

세번째 방법

소수인지 확인하는 자연수의 제곱근을 기준으로 약수들의 곱셉은 대칭적으로 곱셉이 일어나는 패턴이 존재한다. 예시로 24를 기준으로 하면 2 * 12 | 3 * 8 | 4 * 6 | √24 * √24 | 6 * 4 | 8 * 3 | 12 * 2 으로 나타낼 수 있기에 제곱근으로 범위를 줄여 계산하면 시간복잡도는 O(√n)이 된다.

 

#include <iostream>
 
int main()
{
    int n, input, ans;
 
    scanf("%d", &n);
 
    ans = n;
 
    while (n--)
    {
        scanf("%d", &input);
        if (input == 1)
        {
            --ans;
            continue;
        }
 
        for (int i = 2; i * i <= input; ++i)
        {
            if (input % i == 0)
            {
                --ans;
                break;
            }
        }
    }
 
    printf("%d", ans);
}