백준 2023번 신기한 소수

문제 링크입니다: https://www.acmicpc.net/problem/2023

에라토스테네스의 체 원리를 이용하는 문제이지만 메모리가 4MB 밖에 주어지지 않기 때문에 기존 문제들처럼 배열을 통해 소수를 판별하면 메모리 초과가 뜨는 문제였습니다.

따라서 아래와 같이 가지치기(pruning)을 해줘야합니다.

1. 첫 번째로 등장할 수 있는 숫자는 2, 3, 5, 7 뿐입니다.

2. 이 후에는 홀수만 등장할 수 있습니다.

-> 짝수가 등장하면 신기한 소수의 조건을 만족하지 못합니다.

#include <iostream>

using namespace std;

 

int N;

 

bool prime(int num)

{

        if (num == 0 || num == 1)

                 return false;

 

        for (int i = 2; i*i <= num; i++)

                 if (num%i == 0)

                         return false;

        return true;

}

 

void calc(int num, int len)

{

        if (len == N)

        {

                 cout << num << "\n";

                 return;

        }

 

        //홀수만

        for (int i = 1; i <= 9; i += 2)

        {

                 if (prime(num * 10 + i))

                         calc(num * 10 + i, len + 1);

        }

}

 

int main(void)

{

        cin >> N;

 

        calc(2, 1);

        calc(3, 1);

        calc(5, 1);

        calc(7, 1);

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~