C++ 코딩테스트 강좌, 신기한 소수 찾기

안녕하세요, 여러분. 이 강좌에서는 C++을 이용한 코딩 테스트 문제를 풀어보도록 하겠습니다.
주제는 바로 “신기한 소수 찾기“로, 소수에 대한 깊이 있는 이해와 더불어
알고리즘 설계 및 최적화까지 다루어 보겠습니다.

문제 설명

주어진 범위 [L, R] 내의 모든 소수를 찾는 문제입니다.
소수는 1보다 큰 자연수 중에서 1과 자기 자신만을 약수로 가지는 수를 의미합니다.
이번 문제에서는 소수를 찾는 과정에서 다음 두 가지 조건을 충족해야 합니다:

범위 내부의 소수를 찾아야 한다.
각 소수를 출력하기 전에 ‘신기한 소수’인 경우 (“신기한”)라는 문구를 붙여야 한다.

과제를 위해 코드의 시간 복잡도를 고려하면서 효율적으로 소수를 찾아보겠습니다.

입력

두 정수 L, R (1 ≤ L ≤ R ≤ 1000000) 주어집니다.

출력

L과 R 사이의 모든 소수를 출력합니다.
특히, 2 이상의 소수 중에서 그 소수의 모든 자리가 1, 2, 3, 5, 7의 조합으로 이루어진 경우 “신기한”을 출력합니다.

예제

문제 풀이 계획

입력 받은 범위 L과 R을 처리합니다.
Sieve of Eratosthenes 알고리즘을 사용하여 소수를 찾습니다.
신기한 소수를 판별하기 위한 기능을 구현합니다.
찾은 소수를 출력합니다.

알고리즘 설명

소수를 찾기 위해 Sieve of Eratosthenes 알고리즘을 사용할 것입니다.
이 방법은 주어진 범위 내에서 소수를 효율적으로 찾는 데 매우 유용합니다.
알고리즘의 기본 원리는 다음과 같습니다:

2부터 시작하여 각 수를 소수 리스트에 추가합니다.
그 수의 배수를 지움으로써 소수를 걸러냅니다.
이 과정을 범위의 최댓값까지 반복합니다.

C++ 코드 구현


#include <iostream>
#include <vector>
#include <string>

using namespace std;

// 주어진 숫자가 신기한 소수인지 체크하는 함수
bool isMagicalPrime(int num) {
    string s = to_string(num);
    for(char c : s) {
        if(c != '1' && c != '2' && c != '3' && c != '5' && c != '7') {
            return false;
        }
    }
    return true;
}

// 소수를 찾는 Sieve of Eratosthenes 알고리즘
vector<bool> sieve(int maxNum) {
    vector<bool> isPrime(maxNum + 1, true);
    isPrime[0] = isPrime[1] = false; // 0과 1은 소수가 아님
    for(int i = 2; i * i <= maxNum; i++) {
        if(isPrime[i]) {
            for(int j = i * i; j <= maxNum; j += i) {
                isPrime[j] = false;
            }
        }
    }
    return isPrime;
}

int main() {
    int L, R;
    cin >> L >> R;

    vector<bool> prime = sieve(R);
    
    for(int i = L; i <= R; i++) {
        if(prime[i]) {
            cout << i;
            if(isMagicalPrime(i)) {
                cout << " 신기한";
            }
            cout << endl;
        }
    }
    return 0;
}

코드 설명

위의 코드는 두 개의 주요 함수를 포함하고 있습니다:

isMagicalPrime(int num): 주어진 수가 신기한 소수인지 체크합니다.
주어진 숫자를 문자열로 변환하여 각 자리수를 분석합니다.
자리수가 ‘1, 2, 3, 5, 7’ 중 하나인 경우에만 true를 반환합니다.
sieve(int maxNum): Sieve of Eratosthenes 알고리즘을 구현한 함수로,
주어진 최대 숫자까지 소수를 계산하여 bool 벡터를 반환합니다.

결론

이번 강좌에서는 간단한 소수 찾기 문제를 통해 C++ 언어와 자료구조에 대한 감각을 키울 수 있었습니다.
또한 Sieve of Eratosthenes 알고리즘을 실제로 사용하여 효율적인 소수 검색 방법을 체험해 볼 수 있었습니다.
다음 시간에는 좀 더 복잡한 문제를 다루어 보도록 하겠습니다.

내용이 유익하셨다면 댓글로 의견 남겨주세요. 질문 여부도 환영합니다!

문제 설명

입력

출력

예제

문제 풀이 계획

알고리즘 설명

C++ 코드 구현

코드 설명

결론

관련