백준 6219번 C++

백준 6219번 소수의 자격

https://www.acmicpc.net/problem/6219

6219번: 소수의 자격

정답 코드

#include<iostream>
#include<string>
using namespace std;
int arr[4000001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int a,b,k,cnt=0;
    cin>>a>>b>>k;
    arr[0]=1;
    arr[1]=1;
    for(int x=2;x<=4000000;x++){
        if(arr[x]==1)
            continue;
        else{
            for(int y=x*2;y<=4000000;y+=x)
                arr[y]=1;            
        }
    }
    string s=to_string(k);
    for(int x=a;x<=b;x++){
        if(arr[x]==0){
            string str=to_string(x);
            if(str.find(s)!=string::npos)
                cnt++;
        }                
    }
    cout<<cnt;
}

문제 풀이

소수는 에라토스테네스의 체를 이용해서 구했습니다.
배열 인덱스에 해당하는 값이 0이면 소수이고, 1이면
소수가 아닙니다. 그런 다음 D를 문자열로 바꿔주고
배열안의 값들도 비교를 위해서 문자열로 바꿔주었습니다. 이때 to_string()함수를 이용했습니다. 마지막으로 find함수를 통해서 그 값이 있는지 비교 후 cnt를 늘려나갔습니다.