secvente2

#include <fstream>
#include <cmath>
using namespace std;

// rezolvare cu ciurul lui Eratostene

#define NMAX 30001
ifstream f("secvente2.in");
ofstream g("secvente2.out");
int t,n,p,k,m,i,x,D;  // n-atatea numere de pe foaie
                    // p-baza componentei putere a numarului p-prim
                    // -cate numere prime vor fi in secventele cerute
int a[15001]; // a- contine pozitiile numerelor p-prime
int prime[NMAX];
                   // prim[i]=true/false ne va spune daca i este numar prim

void numereprime()                    // ciurul lui Eratostene
{
    int i,j;                  // pentru generarea numerelor prime
    double rad;
    rad=sqrt(NMAX);
    for(i=1;i<=NMAX;i++)    // toate numerele le consideram prime la inceput
        prime[i]=1;
    i=1;                  // plec de la inceputul vectorului
    while(i<=rad)        // se lucreaza doar pana la radical din n
    {
        do
        {
            i++;
        }
        while(!prime[i]);      // caut urmatorul numar prim la rand
        j=i*i;       // primul numar care nu mai este prim este patratul lui
        while(j<=NMAX)      // apoi plecand de la el
        {
            prime[j]=0;    // il marchez ca fiind neprim (e multiplu de i)
            j=j+i;         // si marchez din i in i
        }
    }
}
int pprim(int x)
{
    if(x==1) return 0;   // numarul 1 nu e pprim
    else
    {
        while(x%p==0)    // simplific cu p
            x=x/p;
        return prime[x];  // si verific daca e prim
                         // - de data asta se accepta si 1
    }
}

int main()
{
    numereprime();  //generez tabelul numerelor prime cu ciurul lui Eratostene
    f>>D;
    for(t=1;t<=D;t++)
    {
        f>>n>>p>>k;
        m=0;
        for(i=1;i<=n;i++)
        {
            f>>x;
            if(pprim(x))
            {
                m++;
                a[m]=i;     // am memorat pozitia de aparitie a unui numar p-prim
            }
        }
        if(m-k+1<=0)
            g<<0<<'\n';
        else
            g<<m-k+1<<'\n';      // din m numere prime pot crea m-k+1 secvente de lungime k

        for(i=1;i<=m-k+1;i++)
            g<<a[i]<<' '<<a[i+k-1]<<'\n'; // astea sunt extremitatile secventelor
    }
    f.close();
    g.close();
    return 0;
}