11408 - Count DePrimes

#include<stdio.h>
#include<math.h>
#define M 5000005

bool prime[M];
int DePrime[M];
int genDePrime();
int genprime();

int main()
{
    register int a,b;
    //freopen("in.txt","r",stdin);

    genprime();
    genDePrime();
    while(scanf("%d",&a)&&a)
    {
        scanf("%d",&b);

        printf("%d\n",DePrime[b]-DePrime[a-1]);
    }
    return 0;
}
int genDePrime()
{
    register int i,j,k=0;

    //GENERITING DePrimes

    for(i=2;i<M;i++)
    {
        if(prime[i])
            for(j=i;j<M;j=j+i)
                DePrime[j]+=i;   
    }

    //Counting DePrime
    k=0;
    for(i=2;i<M;i++)
        if(prime[DePrime[i]])
            DePrime[i]=++k;
        else
            DePrime[i]=k;
    return 0;
}

int genprime()
{
    register int i,j,s=sqrt(M);
    for(i=2;i<M;i++)
        prime[i]=true;
    for(i=2;i<s;)
    {
        if(prime[i])
            for(j=i+i;j<M;j+=i)
                prime[j]=false;
        for(i++;!prime[i];i++);
    }
    return 0;
}