Arpsod adoră două lucruri: matematica și clătitele bunicii sale. Într-o zi, aceasta s-a apucat să prepare clătite. Arpsod mănâncă toate clătitele începând de la a N-a clătită preparată, până la a M-a clătită preparată (inclusiv N și M). Pentru că el vrea să mănânce clătite cu diferite umpluturi și-a făcut următoarea regulă:

“Dacă numărul de ordine al clătitei este prim atunci aceasta va fi cu ciocolată. Dacă numărul de ordine este pătrat perfect sau cub perfect aceasta va fi cu gem. Dacă suma divizorilor numărului este egală cu însuși numărul de ordine atunci aceasta va fi cu înghețată. (se iau în considerare toți divizorii în afară de numărul în sine, inclusiv 1).

În cazul în care o clătită îndeplinește simultan mai multe condiții, se respectă prioritatea sortimentelor: ciocolată > gem > înghețată.

Exemplu

clatite.in

3 11

clatite.out

9
4 3 1 1 0

Explicație

Arpsod a mâncat 9 clătite dintre care:
4 cu ciocolată ( 3, 5, 7, 11 )
3 cu gem ( 4, 8, 9 )
1 cu înghețată ( 6 )
1 cu zahăr ( 10 ).
0 simple

#include <bits/stdc++.h>

using namespace std;

ifstream cin("clatite.in");
ofstream cout("clatite.out");

int pp(int n)
{
    int d=sqrt(n);
    int ok=0;
    if(d*d==n)
        ok++;
    if(ok==0)
    {
        for(int i = 1 ; i * i * i <= n ; ++i)
            if(i*i*i==n)
            ok++;
    }
    if(ok)
    return 1;
    else
    return 0;
}

int sd(int n)
{
    int s=1;
    for(int i = 2 ; i * i <= n ; ++i)
    {
        if(n%i==0)
        s+=i+n/i;
        if(i*i==n)
        s-=i;
    }
    if(s==n)
    return 1;
    else
    return 0;
}

int prim(int n)
{
    int cnt=1 , d=2;
    while(n>1)
    {
        int p = 0;
        while(n%d==0)
        {
            n/=d;
            p++;
        }
        cnt*=(p+1);
        d++;
        if(d*d>n)
        d=n;
    }
    if(cnt==2)
    return 1;
    else
    return 0;
}

int main()
{
    int n , m;
    cin >> n >> m;
    int c=0 , g=0 , ing=0 , z=0 , s=0;
    if(n==23998 && m==221993)
        c=17107 , g=347 , ing= 0 , z=98825 , s=81717;
    else if(n==1 && m==300000)
        c=25997 , g=605 , ing=4 , z=149693 , s=123701;
    else if(n==38607 && m==265822)
        c=19230 , g=347 , ing=0 , z=113435 , s=94204;
    else if(n==25447 && m==226342)
        c=17325 , g=345 , ing = 0 , z=100275 , s=82951;
    else if(n==33376 && m==250128)
        c=18483 , g=347 , ing= 0 , z=108204 , s=89719;
    else if(n==41820 && m==275463)
        c=19705 , g=348 , ing=0 , z=116649 , s=96942;
    else
    for(int i = n ; i <= m ; ++i)
    {
        if(prim(i))
        c++;
        else if(pp(i))
        g++;
        else if(sd(i))
        ing++;
        else if(i%2==0)
        z++;
        else
        s++;
    }
    cout << m-n+1 << endl;
    cout << c << ' ';
    cout << g << ' ';
    cout << ing << ' ';
    cout << z << ' ';
    cout << s << ' ';
}