2023 신기한 소수

2023번: 신기한 소수

이 문제를 해결하려면 N자리 수를 모두 생성하고

각각이 신비한 소수라는 조건을 만족하는지에 대해서 검사해야 합니다.

 

N 자리에 도달할 때까지 한 번에 한 자리씩 더하는

재귀 함수를 사용하여 모든 N 자리 숫자를 생성할 수 있습니다.

그런 다음 생성된 각 숫자에 대해 소수성 테스트 기능을 사용하여

모든 접두사 (1자리, 2자리, 3자리 등)가 소수인지 확일할 수 있습니다.

 

숫자가 모든 접두사에 대한 소수 테스트를 통과하면 신비한 소수이며

결과 리스트에 추가하여 출력합니다.

 

1. 소수 체크 함수

bool is_prime(int n) 
{
        if (n < 2) return false;

        // 소수는 제곱근까지만 검사를 해도됨 (4000이면 20까지만 검사)
        for (int i = 2; i * i <= n; i++)
        {
                if (n % i == 0) return false;
        }

        return true;
}

 

2. 숫자 생성 함수

void generate_numbers(int n, int digits, int current, vector<int>& results) 
{
        if (digits == n) 
        {
                results.push_back(current);
                return;
        }

        for (int i = 1; i <= 9; i++) 
        {
                int next = current * 10 + i;
                if (is_prime(next)) 
                {
                        generate_numbers(n, digits + 1, next, results);
                }
        }
}

 

- 매개변수

n : 생성할 숫자의 자릿수

digits : 현재 검사중인 수의 자릿수

current : 현재 검사중인 수

result : 신비한 소수를 담을 리스트

 

generate_numvers 함수의 반복문부터 살펴보면

generate_numbers함수는 첫 실행을 제외하고는 current로 소수를 받게되는데

 

현재 수(current) 에 10을 곱하여 자리를 옮긴 후 ( 7 -> 70 )

1~ 9의 숫자를 더하여 다시 한번 소수를 찾음

이후 해당 수로 재귀하여 자릿수를 늘려감

 

digits가 n과 같게되면 n자리수의 신비한 소수를 찾게된게 되기 때문에

결과 리스트에 현재 값을 추가해줌

 

3. main 함수

int main() 
{
        int n;
        cin >> n;

        vector<int> results;
        generate_numbers(n, 0, 0, results);

        sort(results.begin(), results.end());

        for (int num : results) 
                cout << num << endl;
        

        return 0;
}

generate_numbers함수로 result에 n자릿수의 신비한 소수를 모두 넣어준 후[

algorithm의 sort함수를 통해 오름차순 정렬 후 출력