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

swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWRuoqCKkE0DFAXt&categoryId=AWRuoqCKkE0DFAXt&categoryType=CODE

SW Expert Academy

소수 중에서 해당 숫자가 포함되는지 검사를 해야 한다.

 

우선 1 ~ 1000000까지 소수를 판별한다.

에라토스테네스의 체를 이용하여 소수가 아닌 수를 true로 바꿔주도록 한다.

자세한 설명은 아래 링크로..

eunchanee.tistory.com/18

(프로그래머스 c++)소수 찾기

 

여기서 위의 링크와 다른 점은 소수를 true로 바꿔주지 않는 것이다.

true로 바꿔주면 소수가 아닌 것으로 판단하기 때문에 false로 둔다.

 

D, A, B를 각각 받아오고

A ~ B까지 for문을 돈다.

 

포함 여부를 확인하기 위해 수를 string으로 바꿔주어야 한다.

 

prime 배열에서 해당하는 수가 false인 경우가 소수이다.

각각 string으로 바꿔주고, find 함수를 통해 포함 여부를 확인하면 된다.

#include <iostream>

using namespace std;

bool prime[1000001] = {false, };

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    int t;
    cin >> t;
    
    prime[0] = true;
    prime[1] = true;
    
    for(int i = 2; i <= 1000000; i++)
    {
        if(!prime[i])
        {
            for(int j = i + i; j <= 1000000; j += i)
            	prime[j] = true;
        }
    }
    
    for(int tc = 1; tc <= t; tc++)
    {
        int D, A, B, ans = 0;
        string d;
        cin >> D >> A >> B;
        
        d = to_string(D);
        for(int i = A; i <= B; i++)
        {
            if(!prime[i])
            {
                string p;
                p = to_string(i);
                
                if(p.find(d) != string::npos)
                    ans++;
            }
        }
        cout << "#" << tc << " " << ans << endl;
    }
    return 0;
}