CUBE FREE NUMBERS

SPOJ Problem Set (classical)

9032. Cube Free Numbers

Problem code: CUBEFR

A cube free number is a number who’s none of the divisor is a cube number( A cube number is a cube of a integer like 8(2*2*2) , 27(3*3*3) ). So cube free numbers are 1,2,3,4,5,6,7,9,10,11,12,13,14,15,17,18 etc(we will consider 1 as cube free). 8,16,24,27,32 etc are not cube free number. So the position of 1 among the cube free numbers is 1, position of 2 is 2, 3 is 3 and position of 10 is 9. Given a positive number you have to say if its a cube free number and if yes then tell its position among cube free numbers.

Input:

First line of the test case will be the number of test case T(1<=T<=100000) . Then T lines follows. On each line you will find a integer number n(1<=n<=1000000).

Output:

For each input line, print a line containing “Case I: ”, where I is the test case number. Then if it is not a cube free number then print “Not Cube Free”. Otherwise print its position among the cube free numbers.

Sample Input:

10

1

2

3

4

5

6

7

8

9

10

Sample Output:

Case 1: 1

Case 2: 2

Case 3: 3

Case 4: 4

Case 5: 5

Case 6: 6

Case 7: 7

Case 8: Not Cube Free

Case 9: 8

Case 10: 9


SOLUTION---


#include
#define max 1000002
int main()
{
    //calculating non free cude numbers and store in array b //
    static int b[max];
    static int a[max];
    int i,j,k,t,num,p;
    for(i=2;i
    {
        k=i*i*i;
        if(k>max)
        break;
        else{
        for(j=k;j
            b[j]=1;
          }
        }
    }
    j=2,p=0;
    //storing value of cube frre numbers in array a //
    for(i=2;i
    {
        if(b[i]!=1)
        {
            a[j]=i;
            j=j+1;
        }
    }
    scanf("%d",&t);
    for(i=1;i<=t;i++)
    {
        scanf("%d",&num);
        if(num==1)
            printf("Case %d: 1\n",i);
        else if(b[num]==1)
            printf("Case %d: Not Cube Free\n",i);
        else
        {
            int mid,lb=2,ub=j-1; //here j-1 is the total size of array a//
            // binary search of cube free number in array a //
            while(lb<=ub)
            {
                mid=(lb+ub)/2;
                if(a[mid]==num)
                break;
                else if(a[mid] >num)
                ub=mid-1;
                else
                lb=mid+1;

            }
            printf("Case %d: %d\n",i,mid);
        }
    }
    return 0;
}