4698. 테네스의 특별한 소수

4698. 테네스의 특별한 소수

에라토스테네스의 체를 이용하면 쉽게 풀 수 있는 소수 문제.

main 함수가 실행하고 난 뒤에 곧바로 에라토스테네스의 체를 이용하여 모든 소수를 구할 수 있다.

(이때 1은 따로 처리를 해줘야 한다)

그리고 구해진 소수 중에서 주어진 범위안의 수를 찾고, 그 수가 D라는 숫자를 포함하는지를 검사하면 된다.

<정답 코드>

#include<iostream>
#include<string.h>
#define MAX 1000001
using namespace std;
 
bool isPrime[MAX];
 
void era()
{
    for (int i = 2; i*i < MAX; i++)
    {
        if (isPrime[i])
        {
            for (int j = 2 * i; j < MAX; j += i)
                isPrime[j] = false;
        }
    }
 
}
 
int main()
{
 
    memset(isPrime, true, sizeof(isPrime));
    isPrime[1] = false;
 
    era();            // 에라토스테네스의 체 
    int tc;
    cin >> tc;
    for (int t = 1; t <= tc; t++)
    {
        int A, B, D, ans = 0;
        cin >> D >> A >> B;
 
        for (int i = A; i <= B; i++) {
            if (isPrime[i])
            {
                int num = i;
                while (num != 0)
                {
                    if (num % 10 == D)
                    {
                        ans++;
                        break;
                    }
 
                    num /= 10;
                }
            }
 
        }
 
        cout << "#" << t <<" " <<ans << endl;
 
    }
 
}