Cerința

Se dau n numere naturale prime. Pentru t perechi de numere naturale s şi d să se afle câte numere naturale din intervalul [s,d] sunt divizibile prin cel puţin unul dintre cele n numere prime.

Date de intrare

Fișierul de intrare eratostene8.in conține pe prima linie numerele n şi t, pe a doua linie cele n numere prime, iar pe următoarele t linii câte o pereche de numere s şi d.

Date de ieșire

Fișierul de ieșire eratostene8.out va conține pe linia i răspunsul la întrebarea i, pentru orice i de la 1 la t.

Restricții și precizări

1 ≤ n ≤ 10.000
1 ≤ t ≤ 100.000
1 ≤ s ≤ d ≤ 10.000.000
numerele prime sunt mai mici sau egale cu 1.000.000

Exemplu

eratostene8.in

eratostene8.out

3
2
10

Explicație

Numerele prime date sunt 2 şi 3. În intervalul [1,5] sunt 3 numere divizibile cu 2 sau 3, în intervalul [4,6] sunt 2 numere divizibile cu 2 sau 3, iar în intervalul [5,20] sunt 10 numere divizibile cu 2 sau 3.

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 Eratostene8:

#include <fstream>
#define N 10000000
using namespace std;
ifstream f("eratostene8.in");
ofstream g("eratostene8.out");
int v[N+1];
int n, t, i, j, s, d, p;

int main()
{
    f >> n >> t;
    for(i = 1; i <= n; i++){
        f >> p;
        if(v[p]==0){
            v[p] = 1;
            j = p + p;
            while(j <= N){
                v[j] = 1;
                j = j + p;
            }
        }
    }
    for(i = 1; i <= N; i++)
        v[i] += v[i-1];
    for(i = 1; i <= t; i++){
        f >> s >> d;
        g << v[d]-v[s-1] << "\n";
    }
    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 #3319 Eratostene8

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3319 Eratostene8 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 #3319 Eratostene8