1b_simple_digits

#include <iostream>

using namespace std;

int main() {
    const int ten6 = 1000000;
    int *simpleDigits = new int [ ten6 ], br = 0;

    for(int i = 0; i < ten6; i++ ) simpleDigits[i] = i;
    simpleDigits[1] = 0;

    for(int i = 2; i < ten6; i++ )                          //
        if( simpleDigits[i] !=0 )                           //
            for(int j = i*2; j < ten6; j += simpleDigits[i] ) //
                simpleDigits[ j ] = 0;                      // нулиране <=> задраскване

    for(int i = 2; i < ten6; i++ ) {
        if( simpleDigits[i] !=0 ) br++;
        simpleDigits[i] = br;
    }

    int brAB, xA, xB;
    cin >> brAB;

    while( brAB-- ) {
        cin >> xA >> xB;
        cout << simpleDigits[xB] - simpleDigits[xA-1] << endl;
    }

    delete [] simpleDigits;
    return 0;
}
/*
Задача 1b. Да се напише програма, която намира броя на простите числа в даден затворен интервал.

Вход:
Първото число от входа е броят на примерите на входа. Следващите двойки числа  a и b задават интервала,
в който ще се търси. Двете числа са цели, положителни,  a < b < 106.

Изход:
За всеки пример от входа се извежда на отделен ред намерения брой.

Пример:
3
1 5
13 14
20 22

Решение на примера:
3
1
0
*/