백준 2023 : 신기한 소수 & koi 절단 가능 소수

https://www.acmicpc.net/problem/2023

2023번: 신기한 소수

http://koistudy.net/?mid=prob_page&NO=688&SEARCH=0

KOISTUDY

 

 

에라토스테네스로는 해결이 안된다

 

#include <iostream>
/*
 한 자릿수 중 소수는 2, 3, 5, 7 밖에 없다. 따라서 제일 높은 자릿수의 값은 2, 3, 5, 7만 될 수 있다. 
 (∵오른편 절단 가능 소수이므로)
 
 2. 두 자릿수 이상 넘어가면서 마지막 자릿수 값은 짝수가 될 수 없고(∵2의 배수),
 마찬가지로 5도 될 수 없다(∵5의 배수). 따라서 남는 숫자는 1, 3, 7, 9만 남게 된다. 
 10개의 자릿수를 모두 다 탐색하는 것에 비해 가짓수가 현저히 줄어들게 됨으로 탐색이 빨라진다. (가지치기) 
 
 3. 자릿값을 늘려갈 때 현재 숫자가 소수인지 판별하여 소수인 숫자에만 뒤에 1, 3, 7, 9를 붙여가며 늘려간다. 
 숫자가 커지면 소수 판별에도 시간이 많이 걸리므로 시간을 줄이기 위해 O(sqrt(n))소수 판별 알고리즘을 사용한다.
*/
int n, cnt;
 
int is_prime(int x)
{
    if (x < 2)
    {
        return 0;
    }
    for (int i = 2; i * i <= x; ++i)
    {
        if (x % i == 0)
        {
            return 0;
        }
    }
    return 1;
}
 
void func(int num, int len)
{
    if (len == n)
    {
        if (is_prime(num))
        {
            ++cnt;
            std::cout << num << '\n';
        }
        return;
    }
    else
    {
        if (is_prime(num))
        {
            func(num * 10 + 1, len + 1);
            func(num * 10 + 3, len + 1);
            func(num * 10 + 7, len + 1);
            func(num * 10 + 9, len + 1);
        }
    }
}
 
int main()
{
    std::cin >> n;
    func(2, 1);
    func(3, 1);
    func(5, 1);
    func(7, 1);
    //std::cout << cnt;
}

 

이게 놀라운게 백준은 메모리로 날려버린다지만 koi 저지같은경우 메모리 허용이 되는데, 이 때 에라토스테네스 쓰면 시간초과가 난다.

 

탐색영역의 배제 방식이 dp보다 빠른 경우가 생길수 있다는걸 보여주는 예

 

 

더 괜찮은 소수 판별

 

int is_prime(int x)
{
    if (x < 2)
    {
        return 0;
    }
    for (int i = 3; i * i <= x; i += 2)
    {
        if (x % i == 0)
        {
            return 0;
        }
    }
    return 1;
}

x가 2라면 바로 1을 리턴한다.

 

그 외의 경우라면 계산량을 줄일 수 있다