SPOJ: CUBEFR – Cube Free Numbers

Problem Link

http://www.spoj.com/problems/CUBEFR/

Problem Description

In this problem,we need to find for a given number n whether it is cube free or not. If n is cube free,we need to print its position among cube free numbers.

A number n is cube free if none of the divisors of n is a cube number. 1,2,3,4,5,6,7,9,10,11,12,13 all are cube free while 8,16,24,27,32 are not cube free.

Concepts Used

This problem uses the concept used for marking non primes in prime sieve method.

Code

#include<stdio.h>
#define max 1000000

/*array used for marking primes and later on,for storing cube free numbers*/
long int arr[1000001]={0};

/*array used for marking cube free numbers*/
int cube[1000001]={0};

/*This function marks all the cube free numbers and stores them in arr[],returns the total count of cube free numbers*/
long int  sieve();

long int binsearch(long int,long int,long int);
int main()
{
    long int t,n;
    long int m=sieve();

    /*scan number of test cases*/
    scanf("%ld",&t);

    /*For each test case,scan the value of n. If n is cube free ,print its position else print it is not cube free*/
    for(long int k=0;k<t;k++)
    {
        scanf("%ld",&n);
        if(cube[n]==1)
            printf("Case %ld: Not Cube Free\n",k+1);
        else
        { 
            /*ans stores the index of n in arr[](array of cube free numbers)*/
            long int ans=binsearch(0,m-1,n);

            printf("Case %ld: %ld\n",k+1,ans+1);
        }
    }

    return 0;
}

/*This function marks all the cube free numbers and stores them in arr[],returns the total count of cube free numbers*/
long int sieve()
{
    /*mark all the multiples of 8(1st prime number cube)*/
    for(long int i=8;i<=max;i+=8)
        cube[i]=1;

    /*For each odd number,if it is prime,mark all the multiples of its cube and all the multiples of prime itself.*/    
    for(long int i=3;i*i*i<=max;i+=2)
    {
        if(arr[i]==0)
        {
            long long int a=i*i*i;

            /*mark all the multiples of cube of prime number*/
            for(long int j=a;j<=max;j+=a)
                cube[j]=1;

            /*mark all the multiples of prime numbers*/ 
            for(long int j=i*i;j*j*j<=max;j+=i)
                arr[j]=1;
        }
    }
    long int m=0;

    /*Traverse cube[] array and store all unmarked entries(cube free numbers) in arr[]*/
    for(long int i=1;i<=max;i++)
    {
        if(cube[i]==0)
            arr[m++]=i;
    }

    /*returns the total count of cube free numbers*/
    return m;
}

/*returns index of key in arr[](0-based indexing)*/
long int  binsearch(long int low,long int high,long int key)
{
    while(low<=high)
    {
        long int mid=(low+high)/2;
        if(arr[mid]==key)
            return mid;
        else if(key>arr[mid])
            low=mid+1;
        else
            high=mid-1;
    }
    return -1;
}

Explanation

We need to find whether a given number is cube free or not.If it is not cube free,we need to print its position among cube free numbers. A simple idea is to store all the cube free numbers in an array and then apply binary search on the array to find the position of a given number in the array.

For efficient computation of cube free numbers,we extend the concept used in prime sieve for marking of prime numbers.Please read the post prime sieve for better understanding of this post. The algorithm can be summarised as:

  1. Mark all the multiples of prime number cubes(8,27,125.....).For ex For prime number 2 ,we will mark 8,16,24,32...
  2. We use two arrays arr[] and cube[] .cube[] array is used to mark the cube free numbers and arr[] for marking primes.We need to mark primes because we mark multiples of prime number cubes only.
  3. First we mark all the multiples of 8. For each odd number(starting from 3),we check whether it is prime or not.If it is prime,we mark all the multiples of its cube in cube[]as well as the prime numbers in arr[].
  4. Once we have marked all the cube free numbers in cube[],we can use arr[] to store the cube free numbers(since we do not need the primes now).Simply traverse the cube[] array and if a particular entry is not marked(it is a cube free number),store it in arr[].
  5. For each value of n, we check whether cube[n]=1, if true,n is not cube free,otherwise we perform binary search on arr[] which stores all the cube free numbers.Binary search returns the position of n among all the cube free numbers..

This content has been helpful to you?

Thanks for contributing!

Yes No