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

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema prim003:

#include <iostream>

using namespace std;

int i,k,t,a,b,j,u,p[500011],pr[50000],v[1000001],c[1000001] ;

int main()
{
    p[1] = 1 ;
    p[2] = 0 ;
    k = 0 ;

    for ( i=2 ; i<=500010 ; i++ )
        if ( p[i]==0 )
        {
           k++ ;
           pr[k] = i ;
           j = i+i ;
           while( j<=500010 )
           {
               p[j] = 1 ;
               j = j+i ;
           }
        }
     for( i=1 ; i<=170 ; i++ )
     {
        j=i ;
        u=pr[i]*pr[j] ;
        while( u<=1000000)
        {
            v[u]=1 ;
            j++ ;
            u=pr[i]*pr[j] ;
        }
     };
     c[0]=0 ;
     v[2]=0 ;
     for( i=1 ; i<=1000000 ; i++ )
        if ( v[i]==1 )c[i] = c[i-1]+1 ;
        else c[i] = c[i-1] ;
     cin >> t ;
     for ( i=1 ; i<=t ; i++)
     {
         cin >> a >> b ;
         cout << c[b]-c[a-1] << " " ;
     }
    return 0;
}

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #2325 prim003

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #2325 prim003 de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #2325 prim003