Square Free Number
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, but70 has factors 1, 2, 5, 7, 10, 14, 35 and 70. As none of these are perfect squares (other than 1), 70 is a squarefree number.
For some algorithms, it is important to find out the square free numbers that divide a number. Note that1 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 Format : The only line of the input is a single integer N which is divisible by no prime number larger than 19
Input Constraints : N < 10^9
Output Format : One line containing an integer that gives the number of square-free numbers (not including 1)
Sample Input :
20
Sample Output :
3
Explanation:
- Find out the number which is square free and also the factors are square free..
- We need to find out the count of the square free count in factors.
Code Logic:
- Get input
- Prime factors upto the constraints in a list
- check if the number n%i==0
- if divisible count no.of square free factors
- finally using formula 2**c-1 find square free count.
Program:
Comments
Post a Comment