C Program for Square Free Number

June 24, 2020

C Program for Square Free Number

Square Free Number Codevita Solution

TCS flagship contest, TCS CodeVita, continuosly increasijng its glory ever since its launched. TCS believes that programming can be both fun and productive at the same time. Square Free Number problem is one of the  previous year question, here we have provided a solution in C++ language for the same.

Problem Description

In the theory of numbers, square free numbers have a special place.  A square free number is one that is not divisible by a perfect square (other than 1).  Thus 72 is divisible by 36 (a perfect square), and is not a square free number, but 70 has factors 1, 2, 5, 7, 10, 14, 35 and 70.  As none of these are perfect squares (other than 1), 70 is a square free number.

For some algorithms, it is important to find out the square free numbers that divide a number.  Note that 1 is not considered a square free number. 

In this problem, you are asked to write a program to find the number of square free numbers that divide a given number.

Input:-

  • The only line of the input is a single integer N which is divisible by no prime number larger than 19.

Output:-

  • One line containing an integer that gives the number of square free numbers (not including 1).

Constraints:-

  • N   < 10^9

Complexity:-

  • Simple

Time Limit:-

  • 1

Examples


Example 1

  • Input:-
    20
  • Output:-
    3

Explanation

N=20

If we list the numbers that divide 20, they are

1, 2, 4, 5, 10, 20

1 is not a square free number, 4 is a perfect square, and 20 is divisible by 4, a perfect square.  2 and 5, being prime, are square free, and 10 is divisible by 1,2,5 and 10, none of which are perfect squares.  Hence the square free numbers that divide 20 are 2, 5, 10.  Hence the result is 3.

Example 2

  • Input:-
    72
  • Output:-
    3

Explanation

N=72.  The numbers that divide 72 are

1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72

1 is not considered square free.   4, 9 and 36 are perfect squares, and 8,12,18,24 and 72 are divisible by one of the.  Hence only 2, 3 and 6 are square free.  (It is easily seen that none of them are divisible by a perfect square).  The result is 3.

C Code

#include <stdio.h>
#include <math.h>
int main()
{
    long int n;
    double sqnum;
    long int i,j=0,flag,chksqr,temp[10000];
  	int count=0,k;
  	printf("Enter the number:");
    scanf("%ld",&n);
    
    for(i=2;i<=n/2;i++)
    {
        if(n%i==0)
        {    
            count++;
            sqnum=sqrt(i);
            chksqr=sqnum;
            if(chksqr==sqnum)
            {
                count--;
                temp[j]=i;
                j++;
            }
            else
            {
                for(k=0;k<j;k++) { if(i>temp[k] && j!=0)
                    {
                        if(i%temp[k]==0)
                        {	
                          	count--;
                        	k=j+1;
                        }
                    }
                    else
                        break;
                }
            }
        }
    }

    printf("%d",count);
    return 0;
}
Output
Enter the number : 20
3

Square Free Number Problem in Other Coding Languages

Python

Sorry, we don’t the solution in Python You can provide the solution for this problem in Python, below in the comments sections.

C++

To find the solution of To find the solution of Square Free Number  problem in C++ Programming language click on the button below:

C++

Java

Sorry, we don’t the solution in Java You can provide the solution for this problem in Java, below in the comments sections.

4 comments on “C Program for Square Free Number”


  • 22C017

    import java.io.IOException;

    public class Sq {
    public static void main(String[] args)throws IOException {

    int num = 290990700, a = 0, b = 0, i, j; //62290800
    int[] arr = new int[10000];
    int[] temp = new int[10000];
    for (i = 2; i <= num / 2; i++) {
    if (num % i == 0) {
    arr[a] = i;
    a++;
    }
    }
    //System.out.println(a + " ," + Arrays.toString(arr));
    double d;
    int inte;
    for (i = 0; i < a; i++) {
    d = Math.sqrt(arr[i]);
    inte = (int) d;
    //System.out.println(arr[i]);
    if (d == inte) {
    temp[b] = arr[i];
    b++;
    for (j = i; j < a – 1; j++) {
    arr[j] = arr[j + 1];
    }
    –a;
    }
    }
    //System.out.println(Arrays.toString(arr)+" "+Arrays.toString(temp));
    for (i=0;i<b;i++){
    for (j=0;j<a;j++){
    if (arr[j]%temp[i]==0){
    for (int k = j; k < a – 1; k++) {
    arr[k] = arr[k + 1];
    }
    –a;
    –j;
    }
    }
    }
    System.out.println(a);
    }
    }

    0

  • Utsab

    from math import sqrt
    def isSquareFree(n):
    if n % 2 == 0:
    n = n / 2
    if n % 2 == 0:
    return False
    for i in range(3, int(sqrt(n) + 1)):
    if n % i == 0:
    n = n / i
    if n % i == 0:
    return False
    return True
    num=int(input())
    squarefree=[]
    fac = []
    for i in range(1, num + 1):
    if num % i == 0:
    fac.append(i)
    for i in fac[1:]:
    if isSquareFree(i):
    squarefree.append(i)
    print(len(squarefree))

    0