Baekjoon - Prime Number Qualification

Baekjoon - 6219 : Prime Number Qualification

Before Beginning

The problem to be solved on this post is an application of the algorithm explained in the previous post - The Sieve of Eratosthenes

Prime Number Qualification

Explanation

Given the input A, B & D return how many prime numbers in the range of A - B contains digit D

Input

10 15 3

Output

1
// Since 13 is the only prime number containing number 3

Solution (C++)

#include <iostream>
#include <math.h>
using namespace std;

int A, B, D;
int total = 0;
int current; 
int limit;


int main()
{
    cin >> A >> B >> D;

    bool* isPrime = new bool[B + 1];
    limit = int(sqrt(B));

    for (int i = 0; i <= B; i++)
    {
        isPrime[i] = true;
    }

    isPrime[0] = isPrime[1] = false;

    for (int i = 2; i <= limit; i++)
    {
        if (isPrime[i] == true)
        {
            for (int j = i * i; j <= B; j = j + i)
            {
                isPrime[j] = false;
            }
        }
    }


    for (int i = A; i <= B; i++)
    {
        if (isPrime[i] == true)
        {
            current = i;

            while (current > 0)
            {
                if (current % 10 == D)
                {
                    total = total + 1;
                    break;
                }
                current = current / 10;
            }
        }
    }
    cout << total << "\n";

    return 0;
}