백준 4134번 [다음 소수](C++) -yes6686- 티스토리

백준 문제 풀이: 4134 [다음 소수]

---

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

문제 설명:

입력으로 주어진 정수 n에 대해, n 이상인 첫 번째 소수를 출력하는 문제입니다. 여러 개의 테스트 케이스를 처리해야 하며, 소수 판별은 효율적으로 수행해야 합니다.

---

문제 해결 코드

#include <iostream>
using namespace std;

// 소수 판별 함수
bool is_prime(long long n) {
    if (n <= 1) return false; // 1 이하의 숫자는 소수가 아님
    for (long long i = 2; i * i <= n; i++) {
        if (n % i == 0) return false; // 약수가 존재하면 소수가 아님
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int T; // 테스트 케이스 수
    cin >> T;

    while (T--) {
        long long n;
        cin >> n;

        // n 이상인 첫 번째 소수를 찾음
        while (!is_prime(n)) {
            n++;
        }
        cout << n << '\n'; // 결과 출력
    }

    return 0;
}

예제 입력:

3
6
20
100

예제 출력:

7
23
101

---

코드 설명

• 핵심 알고리즘: 주어진 수 이상인 소수를 효율적으로 찾기 위해 소수 판별 알고리즘을 사용합니다.
• 구현 세부사항:
  • is_prime 함수는 주어진 숫자가 소수인지 판별합니다. 숫자 i를 2부터 √n까지 검사하여 약수가 있는지 확인합니다.
  • 입력된 수 n이 소수가 아니라면, 1씩 증가시키며 첫 번째 소수를 찾습니다.
• 시간 복잡도:
  • 소수 판별: O(√n)
  • 최악의 경우: O(T ⋅ √n), 여기서 T는 테스트 케이스 수입니다.

---

결과

입력된 각 테스트 케이스에 대해, 주어진 정수 이상인 첫 번째 소수를 정확히 출력합니다. 이 문제는 소수 판별 및 반복 처리의 효율성을 연습하기에 적합합니다. 추가적인 질문이나 개선 사항이 있다면 댓글로 알려주세요!