[백준] 6219번 : 소수의 자격 (C++)

6219번 : 소수의 자격

---

문제)

농부 존은 소들에게 소수로 차례차례 번호를 매기는 중이다. 베시는 이 번호에서 숫자 D가 몇 번이나 등장하는지 궁금해졌다.

베시를 도와 범위 A..B(A와 B 포함)내에서 숫자 D를 포함하는 소수의 개수를 구해보자.

소수는 두개의 자연수(1과 자기자신)로만 나누어 떨어지는 자연수를 말한다. 소수의 예로는 2,3,5,7,11,13,17,19,23,29.. 가 있다.

 

 

 

입력 :

세 정수 A, B, D가 주어진다.

 

 

 

 

출력 :

주어진 범위 내에서 숫자 D를 포함하는 소수의 개수를 출력한다.

 

 

 

 

 

 

 

풀이)

// 6219. 소수의 자격
#include <iostream>
#include <vector>
#include <string>
 
using namespace std;
 
long long a, b;
char d;
vector<bool> vec;
 
// 에라토스테네스의 체 이용 b까지의 소수를 모두 찾는다.
void isPrime()
{
    vec[1] = false;
 
    for (long long i = 2; i <= b; i++)
    {
        if (!vec[i]) continue;
        for (long long j = 2 * i; j <= b; j += i)
        {
            vec[j] = false;
        }
    }
}
 
int main()
{
    cin >> a >> b >> d;
    vec.resize(b + 10, true);
    isPrime();
 
    int cnt = 0;
 
    for (int i = a; i <= b; i++)
    {
        // 만약 해당 수가 소수라면
        if (vec[i] == true)
        {
            // 해당 수 안에 d가 있는지 확인한다.
            string temp = to_string(i);
            for (int j = 0; j < temp.length(); j++)
            {
                if (temp[j] == d)
                {
                    cnt++;
                    break;
                }
            }
        }
    }
 
    cout << cnt;
 
    return 0;
}

---

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

6219번: 소수의 자격