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
'BAEKJOON > 수학' 카테고리의 다른 글
백준 2292번 [벌집](C++)-yes6686- 티스토리 (0) | 2024.01.02 |
---|---|
백준 2108번 [통계학](C++)-yes6686- 티스토리 (0) | 2024.01.02 |
백준 1929번 [소수 구하기](C++)-yes6686- 티스토리 (1) | 2024.01.02 |
백준 1676번 [팩토리얼 0의 개수](C++)-yes6686- 티스토리 (0) | 2023.12.21 |
백준 1546번 [평균](C++)-yes6686- 티스토리 (0) | 2023.12.21 |