본문 바로가기

BAEKJOON/수학

백준 1978번 [소수 찾기](C++)-yes6686- 티스토리

728x90
SMALL

백준 문제 풀이: 1978 [소수 찾기]


문제 링크: https://www.acmicpc.net/problem/1978

문제 설명:

주어진 n개의 숫자 중에서 소수인 숫자의 개수를 구하는 문제입니다. 소수는 1과 자기 자신만으로 나누어 떨어지는 숫자를 의미합니다.


문제 해결 코드


#include <iostream>
using namespace std;

int main() {
    int n;
    int x;
    int cnt = 0;
    int result = 0;
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        for (int j = 1; j <= x; j++) {
            if (x % j == 0) {
                cnt++;
            }
        }
        if (cnt == 2) {
            result++;
        }
        cnt = 0;
    }
    cout << result;
}

코드 설명

  • 입력: 첫 번째로 입력받은 숫자 n은 체크해야 할 숫자의 개수를 의미하며, 그 다음에는 숫자 리스트가 입력됩니다.
  • 로직:
    • 각 숫자에 대해, 1부터 해당 숫자까지 나누어떨어지는 경우를 카운트합니다.
    • 나누어떨어지는 경우가 정확히 2번이라면(1과 자기 자신), 해당 숫자는 소수로 간주하고 결과를 증가시킵니다.
  • 출력: 소수의 개수를 출력합니다.

시간 복잡도

코드는 각 숫자에 대해 모든 약수를 확인하기 때문에 시간 복잡도는 O(n * x), 여기서 n은 입력받은 숫자의 개수, x는 숫자 하나의 크기입니다. 숫자가 클수록 비효율적일 수 있습니다.


결과

주어진 숫자 리스트에서 소수의 개수를 정확히 계산합니다. 이 코드는 단순하고 직관적이지만, 숫자가 매우 큰 경우 효율성을 개선하기 위해 에라토스테네스의 체와 같은 더 빠른 소수 판별 알고리즘을 활용할 수 있습니다.

혹시 이 문제를 풀면서 더 효율적인 알고리즘을 고민해 보셨나요? 공유해 주시면 재미있게 이야기 나눠봐요!

728x90
LIST