numbers_tree_50p

#include <bits/stdc++.h>
#include <cstring>
#define N 1000001
using namespace std;
bool *isPrime=new bool[N];

/// Ciurul lui Atkin (Sieve of Atkin) este un algoritm rapid si modern de gasire a tuturor numerelor prime pana la un numar întreg. A fost creat de A.O.L. Atkin si Daniel J. Bernstein.
void Atkin(int lim)
{
    /// Initial toate numerele sunt neprime
    memset(isPrime,0,sizeof(bool)*(lim+1));
    double sqr=sqrt(lim);
    int n;
    for(int x=1;x<=sqr;++x)
    {
        for(int y=1;y<=sqr;++y)
        {
            n=4*x*x+y*y;
            if(n<=lim&&(n%12==1||n%12==5))
                isPrime[n]=!isPrime[n];
            n=3*x*x+y*y;
            if(n<=lim&&n%12==7)
                isPrime[n]=!isPrime[n];
            n=3*x*x-y*y;
            if(x>y&&n<=lim&&n%12==11)
                isPrime[n]=!isPrime[n];
        }
    }
    for(int i=5;i<=sqr;i+=2)
    {
        /// Daca este prim, marcheaza toti multiplii i*i ca fiind neprimi
        if(isPrime[i])
        {
            for(int k=i*i;k<=lim;k+=i*i)
            isPrime[k]=false;
        }
    }
}

#define DIM 262144
char buff[DIM];
int poz=0;
FILE *f=fopen("numbers_tree.in","r");

void citeste(int &numar)
{
     numar=0;
     while(buff[poz]<'0'||buff[poz]>'9') /// cat timp caracterul din buffer nu e cifra ignor
          if (++poz==DIM) ///daca am "golit" bufferul atunci il umplu
               fread(buff,1,DIM,f),poz=0;
     while('0'<=buff[poz]&&buff[poz]<='9') ///cat timp dau de o cifra recalculez numarul
     {
          numar=numar*10+buff[poz] - '0';
          if(++poz==DIM)
               fread(buff,1,DIM,f),poz=0;
     }
}

int main ()
{
    Atkin(N);
    isPrime[2]=1;
    isPrime[3]=1;
    isPrime[5]=1;
    int n,q;
    citeste(n),citeste(q);
    int a[n+1];
    for(int i=1;i<=n;++i)
        citeste(a[i]);
    int op=0,st,dr,val;
    ofstream g("numbers_tree.out");
    while(q--)
    {
        citeste(op),citeste(st),citeste(dr);
        if(op==1) /// toate valorile a[i] cu i din intervalul [st,dr] devin egale cu val
        {
            citeste(val);
            for(int i=st;i<=dr;++i)
                a[i]=val;
        }
        if(op==2) /// cate elemente ale sirului a care au indicii aflati in intervalul [st, dr] sunt numere compuse
        {
            int sol=0;
            for(int i=st;i<=dr;++i)
                if(!isPrime[a[i]]) /// Daca nu sunt prime, atunci sunt compuse
                    ++sol;
            g<<sol<<'\n';
        }
        if(op==3) /// lungimea celei mai lungi secvente de numere prime alcatuita exclusiv din elemente ale sirului care au indicii aflati in intervalul [st, dr]
        {
            int k=0,Max=-1;
            for(int i=st;i<=dr;++i)
            {
                if(isPrime[a[i]])
                    ++k;
                else
                    k=0;
                if(k>Max)
                    Max=k;
            }
            g<<Max<<'\n';
        }
    }
    return 0;
}