prime003

#include <fstream>
#include <bitset>
#define N 10000001
using namespace std;
bitset <N> prim;

void Ciur()
{
    prim[0]=prim[1]=1; /// Ciurul lui Eratostene
    for(int i=2;i*i<N;++i)
        if(prim[i]==0)
            for(int j=2;i*j<N;++j)
                prim[i*j]=1;
}

/// Folosind Ciurul lui Eratostene se afla numerele prime de la 1 la 10.000.000, afland in acelasi timp si secventele de numere neprime
/// (care sunt cuprinse intre doua numere prime consecutive). La fiecare pozitie din sirul numerelor naturale se retine pozitia de inceput
/// a secventei si lungimea secventei de numere neprime.

int main()
{
    ifstream f("prim997.in");
    ofstream g("prim997.out");
    int n;
    f>>n;
    int a[n];
    for(int i=0;i<n;++i)
        f>>a[i];
    f.close();
    Ciur();
    int j,L,Lmax,primul,primulMax;
    bool ok;
    for(int i=0;i<n;++i)
    {
        j=1;
        while(j<=a[i])
        {
            L=0;
            Lmax=0;
            ok=true;
            for(int j=1;j<=a[i];++j)
                if(prim[j])
                {
                    ++L;
                    if(ok)
                        primul=j,ok=false;
                }
                else
                {
                    if(L>Lmax)
                        Lmax=L,primulMax=primul;
                    L=0;
                    ok=true;
                }
            ++j;
        }
        g<<primulMax<<' '<<Lmax<<'\n';
    }
    return 0;
}