[C++] 백준 알고리즘 1978번 (소수 찾기)

문제

 

---

이번에 다뤄볼 문제는 1978번 문제 '소수 찾기'입니다.

소수 찾기 문제에서 연습해야 할 key-point는 소수찾는법을 암기하는것 입니다.

 

네이버에서 알고리즘 포스팅을 했을때 예상외로 많은 조회수를 올린 문제가 바로 이 소수찾기 문제였습니다.

소수는 모두가 잘 알고있듯, 약수가 1과 자기 자신밖에 없는 수를 칭합니다.

 

만약 입력된 N값이 소수가 아니라면 N = a x b (a<=b) 로 표현될 수 있습니다. 이때 a와 b의 차이가 가장 작은 경우는 루트 N이기 때문에 여기까지만 검사를 해서 이 숫자가 소수인지 판별하면 되는데요.

 

소수 찾기문제는 위에서 설명한 루트 N까지 탐색하며 소수판별을 하는 함수를 하나 만들어서 쉽게 해결 할 수 있습니다.

탐색 범위는 아래와 같이 3가지로 구현할 수 있습니다.

for (int i = 2; i <= x-1; i++)
for (int i = 2; i <= x/2; i++)
for (int i = 2; i*i <= x; i++)

상황에 따라 위 3가지 중 하나를 택해서 사용하면 됩니다. 하지만 통상적으로 위에서 얘기한 루트 N까지의 탐색범위인 3번라인을 택하여 문제를 풉니다.

 

아래 해답 코드를 보면 더 쉽게 이해할 수 있으실 겁니다.

---

 

코드(C++)

#include<iostream>
using namespace std;
 
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 arr[101];
    int n;
    int count = 0;
 
    cin >> n;
    for (int i = 0; i <= n - 1; i++) {
        cin >> arr[i];
        if (prime(arr[i]) == true) count++;
    }
 
    cout << count << endl;
 
    return 0;
}