Question

Cerința
Anul 2017 tocmai s-a încheiat, suntem trişti deoarece era număr prim, însă avem şi o veste bună, anul 2018 este produs de două numere prime, 2 şi 1009. Dorel, un adevărat colecţionar de numere prime, şi-a pus întrebarea: “Câte numere dintr-un interval [a,b] se pot scrie ca produs de două numere prime? “.

Date de intrare
Programul citește de la tastatură numărul natural t, iar apoi t perechi de numere naturale a,b cu a≤b, separate prin spații.

Date de ieșire
Programul va afișa pe ecran, pentru fiecare pereche a,b, numărul numerelor din intervalul [a,b] care se pot scrie ca produs de două numere prime.

Restricții și precizări
1 ≤ t ≤ 100.000
1 ≤ a ≤ b ≤ 1.000.000

Exemplu
Intrare

3
1 7
10 30
88 100
Ieșire

2 7 4
Explicație
În intervalul [1,7] sunt 2 numere ce se pot scrie ca produs de două numere prime: 4 şi 6. În intervalul [10,30] sunt 8 numere: 10,14,15,21,22,25,26. În intervalul [88,100] sunt 4 numere: 91,93,94,95.

Answer 1

#include <bits/stdc++.h>
using namespace std;
int t, i, a, b, j, nr, dif, v[1000005];
void ciur(){    for(i=2; i<1000000; i++)        if(!v[i])        {            dif=1;            for(j=i; j<=1000000; j+=i)            {                if(j%(i*i)==0)                {                    dif++;                    v[j]+=dif;                }                else                    v[j]++;            }        }}int suma[1000002];int main(){    ciur();    for(i=1;i<=1000001;++i)        {suma[i]=suma[i-1];        if(v[i]==2)++suma[i];}    cin >> t;    for(i=1; i<=t; i++)    {        cin >> a >> b;        cout << suma[b]-suma[a-1]<< " ";    } return 0;}