UVA 11408 - Count DePrimes Solution

Problem Statement
 A number is called a DePrime if the sum of its prime factors is a prime number.

Given a and b count the number of DePrimes xi such that axib .

Input 

Each line contains a and b in the format ``a b ". 2a5000000 . ab5000000 .

Input is terminated by a line containing `0'.

Output 

Each line should contain the number of DePrimes for the corresponding test case.

Explanation:

In Test Case 2, take 10. Its Prime Factors are 2 and 5. Sum of Prime Factors is 7, which is a prime. So, 10 is a DePrime.

Sample Input 

2 5
10 21
100 120
 0

Sample Output 

4
9
9
C/C++ Implementation of this problem.

#include<iostream>

using namespace std;
#define MX 5000005
#define hi 2241
long prime[MX+5];
long factor[500],n_prime,table[MX+5];
void sieve(){
 long i,j;

 n_prime=0;
 memset(prime,0,sizeof(prime));
 prime[0]=prime[1]=0;
 for(i=4;i<=MX;i+=2)
 
 prime[i]=2;
 table[0]=table[1]=0;
 table[2]=1;
 for(i=3;i<=MX;i++){
  table[i]=table[i-1];
  if(!prime[i]){  
   table[i]++;
   for(j=i+i;j<=MX;j+=i)
    prime[j]+=i;
  }
  else if(!prime[prime[i]])
   table[i]++;
 }
}
int main(){
 long a,b;
 sieve();

 while(scanf("%ld",&a)&&a){
  scanf("%ld",&b);
  printf("%ld\n",table[b]-table[a-1]);
 }
 return 0;
}