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

1. 문제 상세

 

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

 

 

 

2. 문제 접근

 

소수는 자기 자신과 1만을 약수로 가지는 수이다.

 

입력받은 N 개의 숫자가 소수인지 확인하여 소수인 숫자의 개수를 알아내자.

일단 이를 위해 각 숫자가 소수인지를 확인해야 한다.

입력받은 숫자가 X 라고 하자, 이 X 가 소수인지 확인하기 위한 방법을 크게 3가지로 꼽아봤다.

 

1. X를 2부터 X - 1의 수까지 나누어 보며 나머지가 0이 아닌지 확인하는 방법이 있다.

하지만 이 방법은 2부터 X - 1 까지의 수를 전부 나누어 봐야 하기 때문에 연산 횟수가 많다.

 

2. X를 2 부터 X / 2 의 수까지 나누어 보며 나머지가 0이 아닌지 확인하는 방법이다.

X를 나눌 때, X를 제외하고 X의 절반이 넘는 수로 나눈 경우엔 나머지가 0이 될 수 없다.

따라서 X의 절반이 넘는 수는 연산하지 않도록 한다.

 

3. X 를 X 의 가운데 약수, √X 까지 나누어 보며 0이 아닌지 확인하는 방법.

약수들은 가운데 약수를 기준으로 대칭 형태를 보이고 있다.

예를 들어 12의 약수를 확인 해 볼 때

 

1 x 12

2 x 6

3 x 4

4 x 3

6 x 2

12 x 1

 

위 와 같이 3 을 기준으로 대칭 형태이다.

따라서 X 를 2부터 √X 까지의 수로 나누어 보며 0이 아닌지 확인하면 되는데,

제곱근 연산을 하기보다 나눌 수를 제곱하여 X 이하인지 확인하는 방법이 편하다.

 

위 세가지 방법을 볼 때 연산 횟수를 비교하면 3번째 방법이 가장 효율적임을 알 수 있다.

 

이제 문제 해결을 위해 입력받은 수들을 하나씩 확인해보고 맞다면 카운트를 증가, 모두 확인하고 카운트를 출력하자.

 

 

 

3. 문제 풀이

 

#include <iostream>
using namespace std;

int main() {
    int n, num, count = 0;
    
    cin >> n;
    
    for(int i = 0; i < n; i++) {
        cin >> num;
        if(num == 1) continue;
        count++;
        
        for(int j = 2; j * j <= num; j++) {
            if(num % j == 0) {
                count--;
                break;
            }
        }
    }
    
    cout << count;
}

 

정수형 변수 n, num, count 를 선언하고 count 를 0으로 초기화한다.

 

cin 으로 정수(입력받을 수의 개수)를 입력받아 n 에 저장한다.

 

for문으로 i 가 0부터 n 보다 작을 때 1씩 더하며 반복하도록 한다.반복에서는 cin 으로 숫자를 입력받아 num 에 저장한다.if문으로 num 이 1이라면 continue 로 이번 반복을 건너뛰도록 한다.count 에 1을 더해준다.

 

for문으로 j 가 2부터 j 의 제곱 값이 num 보다 작거나 같을 때 1씩 더하며 반복하도록 한다.반복에서는 if문으로 num 을 j 로 나눈 나머지가 0일 때 count 의 값을 1감소시키고 break 로 반복을 빠져나온다.

 

모든 반복이 끝나면 count 를 출력한다.

 

 

 

4. 성능 확인

 

 

 

 

5. 마무리

 

소수의 판별 알고리즘에 대해 알아보았다.

이번 문제를 다 풀고 알게 되는 바람에 사용하지 않았지만,

에라토스테네스의 체 알고리즘을 사용하면 제시한 방법들보다 더욱 빠르게 연산이 가능하다.

제한시간이 짧아지는 경우 연산 횟수를 줄이기 위해 사용해야 할 수도 있겠다.

 

이번 문제에서 해당 알고리즘을 사용했다고 한다면,

에라토스테네스의 체 알고리즘을 통해 1000까지의 수들 중 소수를 판별한 배열을 만들어놓고

입력받은 수를 배열 인덱스로 바로 참조하여 배열 값을 통해 그 수가 소수인지 아닌지 확인하면 된다.

확인 후 카운트를 통해 소수의 개수를 출력하면 끝.

 

위 알고리즘을 통해 문제를 해결해봐도 좋았을 것 같은데 아쉽다.

 

다음 소수 판별 문제에서는 에라토스테네스의 체 알고리즘을 활용해보자