Square Free Numbers - CodeVita 9 | Round 1

Square Free Numbers

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).

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

Other Test Case

Input
290990700

Output
255

Input
4491411836

Output
31

Program:

#include <stdio.h>

int isPerfectSquare(int n) 

{ 

    for (int i = 1; i * i <= n; i++) 

    { 

        if ((n % i == 0) && (n / i == i)) 

        { 

            return 1; 

        } 

    } 

    return 0; 

} 

int main() {

int x,i,cnt=0,j=0,y,k,a[10000];

scanf("%d",&x);

for(i=1;i<=x;i++)

{

    if(x%i==0)

    {

        a[j]=i;

        j++;

    }

}

for(i=0;i<j;i++)

{

    if((isPerfectSquare(a[i])==1)&&(a[i]!=0)&&(a[i]!=1))

    {

      y=a[i];

      for(k=0;k<j;k++)

      {

        if(a[k]!=0 && a[k]%y==0)

        a[k]=0;

       }

        a[i]=0;

     }

}

for(i=0;i<j;i++)

if(a[i]!=0)

cnt++;

printf("%d",cnt-1);

return 0;

}

You can also run it on an online IDE:    

https://ide.geeksforgeeks.org/tttw8dQwDN

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

Related Links:

Grooving Monkeys: https://codepiggy.blogspot.com/2020/03/grooving-monkeys-code-vita-8-pre.html

Parallelograms | Code Vita 2018 | round 1

Parallelograms

Problem Description

A number (N) of lines (extending to infinity) in both directions are drawn on a plane. The lines are specified by the angle (positive or negative) made with the x axis (in degrees). It may be assumed that the different lines are not coincident (they do not overlap each other). The objective is to determine the number of parallelograms in the plane formed by these lines.

If the lines are given with an angle of 10, 70, 30 and 30, the figure looks like this

L1 is at 10 degrees to the x axis, L2 is at 70 degrees to the x axis, L3 and L4 are at 30 degrees to the x axis. It can be seen that there are no parallelograms formed by these lines

Constraints

N<=50

-89 <= angle for any line <=90

Input Format

The first line of the input consists of a single integer, N.

The next line consists of a series of comma separated integers (positive, zero or negative), each corresponding to a separate line, and giving the angle that it makes with the x axis (in degrees).

Output

The output is a single integer giving the number of parallelograms in the plane formed by the lines

Explanation

Example 1

Input

5

20,20,-20,-20,50

Output

1

Explanation

There are 5 lines (N=5), with angles at 20,20,-20,-20and 50 degrees with the x axis. The figure looks like this

There is one

Hence the output is 1.

Example 2

Input

6

20,20,-20,-20,50,50

Output

3

Explanation

There are 6 lines (N=6) with angles 20,20, -20,-20,50 and 50 degrees with the x axis.. The figure looks like this

There are three parallelograms formed by (L1, L2, L3, L4), (L1, L2, L5, L6) and (L3, L4, L5, L6). Hence the output is 3.

Program:

#include<stdio.h>
int pairfound(int angle[],int i,int n)
{
  int j;
  for(j=i+1;j<n;j++)
  {
    if(angle[i]==angle[j])
      return 1;
  }
  return 0;
}
int main()
{
  int n,i,count=0,pllgm,ang;
  scanf("%d",&n);
  int angle[n];
  for(i=0;i<n;i++)
  {
    scanf("%d,",&ang);
    if(ang>=-89&&ang<=90)
        angle[i]=ang;
  }
  for(i=0;i<n;i++)
  {
    if(pairfound(angle,i,n)==1)
    {
      count++;
    }
  }
  pllgm=(count-1)*count/2;
  printf("%d",pllgm);
  return 0;
}


Output

6

20,20,-20,-20,50,50

3

You can also try it in online IDE: https://ide.geeksforgeeks.org/vVEgz35Wso

Your comments and feedback are welcomed! You can contact me if you have any doubts! Cheers!



Related Links: Reverse Gear