[C++] 백준 6219 - 소수의 자격

문제 - 소수의 자격 (Silver3)

[백준 6219] https://www.acmicpc.net/problem/6219

풀이 전략

• 매번 소수 관련 문제를 풀 때처럼 에라토스테네스의 체를 이용해서 소수를 걸러준 뒤 시작한다.
• 숫자에 D가 포함되었는지 확인해야되기 때문에 hasDigit 함수를 만들어서 확인한 뒤 T/F를 반환하도록 한다.
• A,B 범위 사이의 숫자가 소수이면서 hasDigit 함수에서 True를 반환한다면 count를 늘려주고 반복문이 종료되면 count를 출력한다.

소스 코드

#include <iostream>
#include <vector>
#include <cmath>

const int MAX_NUM=4000001;
using namespace std;

bool hasDigit(int number, int digit) {
    while(number>0){
        if (number%10==digit){
            return true;
        } // 1의 자리수에 digit (D)가 포함되어있는지 확인
        number/=10;
        // 1의 자리수를 확인한 뒤, 10의 자리로 넘어감
    }
    return false;
}
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int A,B,D;
    cin>>A>>B>>D;

    vector<int> Prime(MAX_NUM+1,1);
    Prime[0]=Prime[1]=0;

    for(int i=2;i<=sqrt(MAX_NUM);i++){
        for(int j=i*i;j<=MAX_NUM;j+=i){
            Prime[j]=0;
        }
    } // 에라토스테네스의 체
    
    int count=0;
    for(int i=A;i<=B;i++){
        if(Prime[i]==1 && hasDigit(i,D)){
            count++;
        } // i가 소수이면서 hasDigit==True이면 count++
    }
    cout<<count<<'\n';
    return 0;
}

결과

30 38 3의 경우, 반례를 확인하기 위해 임의로 해본 케이스인데, 30과 38 사이에 소수가 31과 37 2개가 있고, 3을 2개 갖고 있으므로 2를 출력하는 결과가 맞다.