Prime Counters - Code Vita 2017 | Round 1

Prime Counters

Problem : 

Given a number N, let CP(N) denote the number of primes between 1 and N (inclusive of N). We call N a prime counter if CP(N) is a prime (N need not be a prime).  For example, CP(3) = 2, CP(4) = 2, CP(5) = 2, CP(7) = 4.

Input Format:  

An integer T, number of test cases  T lines each containing two positive integers L, R separated by space

Output Format:  

T lines containing the number of prime counters between L and R (both inclusive) in the ith test case (or NONE is no prime counter exists in that range)

Constraints:  

L ≤ R ≤ 106

Example 1 

 Input  1

  1 10

Output 
 4

Explanation 
CP(1) = 0, CP(2) = 1, CP(3) = 2, CP(4) = 2, CP(5) = 3, CP(6) = 3, CP(7) = 4= CP(8) = CP(9) = CP(10)   Hence there are 4 prime counters, 3, 4, 5, 6 in the range 1 to 10.

Example 2  

Input  2

 2 20  3 30 

Output  

  8
 8

Explanation  
Upto 10, we have 4 prime counters. Between 11 and 20 the prime counters are 11, 12, 17, 18 and hence the count is 8. Between 21 and 30, we have no prime counters.

Program:

#include <stdio.h>
int prime(int n)
{
    int k,j,p=0;
    for(k=2;k<=n;k++)
    {
        int c=0;
        for(j=1;j<=k;j++)
            if(k%j==0)
            c++;
       if(c==2)
        p++;
    }
    return p;
}
int main() 
{
int l,t,r,i,cp[1000],k,f,c=0,j,count;
scanf("%d",&t);
for(int z=1;z<=t;z++)
{
count=0;
scanf("%d %d",&l,&r);
for( i=l;i<=r;i++)
   cp[i]=prime(i);
for(j=l;j<=r;j++)
{
    c=0;
    for (k = 1;k<=cp[j]*cp[j];k++) 
    {
          if (cp[j] % k == 0) 
            c++;
        }
        if (c == 2) 
        count++;
}
printf("%d\n",count);
}
return 0;

}

You can also run it on an online IDE: https://ide.geeksforgeeks.org/YphGa2McDy

Your feedback are always welcome! If you have any doubt you can contact me or leave a comment!! Cheers!!!

Related Links:
Air in the balloon: https://codepiggy.blogspot.com/2020/03/air-in-balloons.html