SWEA 4698. 테네스의 특별한 소수 (C++)

A B 숫자 사이에서 D를 포함한 소수를 찾는 문제!!

핵심!! 에라토스테네스의 체 이용!!

※ 에라토스테네스의 체란 숫자의 배수를 제거하여 소수를 식별하는 방법!!

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

#include <stdio.h>

int D, A, B;
bool primeNum[1000001];
int answer;
void Eratos(int n)
{
    for (int i = 2; i <= n; i++)
    {
        primeNum[i] = true;
    }

    for (int i = 2; i*i <= n; i++)
    {
        if (primeNum[i])
        {
            for (int j = i * i; j <= n; j += i)
            {
                primeNum[j] = false;
            }
        }
    }
}

void solve()
{
    for (int i = A; i <= B; i++)
    {
        if (!primeNum[i])
            continue;

        int num = i;
        while (num)
        {
            if (num % 10 == D)
            {
                answer++;
                break;
            }
            else
            {
                num = num / 10;
            }
        }
    }
}

int main()
{
    Eratos(1000000); // 에라토스테네스의 체

    int tc = 0;
    scanf("%d", &tc);

    for (int t = 1; t <= tc; t++)
    {
        answer = 0;
        scanf("%d %d %d", &D, &A, &B);
        solve();
        printf("#%d %d\n", t, answer);
    }
    return 0;
}

 

1. Eratos함수를 이용해 primeNum 배열에 소수를 저장

2. 각 자릿수의 숫자와 D를 비교

3. 끝