Count number less than N which are product of perfect squares
Given an Integer N. The task is to count numbers P less than N such that P is a product of two distinct perfect squares.
Examples:
Input : N = 36 Output : 5 Numbers are 4 = 12 * 22, 9 = 12 * 32, 16 = 12 * 42, 25 = 12 * 52, 36 = 12 * 62
Input : N = 1000000 Output : 999
Approach: Let us consider a number P = (a2 * b2) such that P <= N. So we have (a2 * b2) <= N. This can be written as (a * b) <= sqrt(N).
So we have to count pairs (a, b) such that (a * b) <= sqrt(N) and a <= b.
Let us take a number Q = (a * b) such that Q <= sqrt(N).
Taking a = 1, we have b = sqrt(N) – 1 numbers such that, ( a * b = Q <= sqrt(N)).
Thus we can have all sqrt(N) – 1 numbers such that (a2 * b2) <= N.
Below is the implementation of the above approach:
C++
// C++ program to count number less // than N which are product of // any two perfect squares #include <bits/stdc++.h> using namespace std; // Function to count number less // than N which are product of // any two perfect squares int countNumbers( int N) { return int ( sqrt (N)) - 1; } // Driver program int main() { int N = 36; cout << countNumbers(N); return 0; } |
Java
// Java program to count number less // than N which are product of // any two perfect squares import java.util.*; class solution { // Function to count number less // than N which are product of // any two perfect squares static int countNumbers( int N) { return ( int )Math.sqrt(N) - 1 ; } // Driver program public static void main(String args[]) { int N = 36 ; System.out.println(countNumbers(N)); } } //This code is contributed by // Surendra_Gangwar |
Python 3
# Python 3 program to count number # less than N which are product of # any two perfect squares import math # Function to count number less # than N which are product of # any two perfect squares def countNumbers(N): return int (math.sqrt(N)) - 1 # Driver Code if __name__ = = "__main__" : N = 36 print (countNumbers(N)) # This code is contributed # by ChitraNayal |
C#
// C# program to count number less // than N which are product of // any two perfect squares using System; class GFG { // Function to count number less // than N which are product of // any two perfect squares static int countNumbers( int N) { return ( int )(Math.Sqrt(N)) - 1; } // Driver Code public static void Main() { int N = 36; Console.Write(countNumbers(N)); } } // This code is contributed // by Akanksha Rai |
PHP
<?php // PHP program to count number less // than N which are product of // any two perfect squares // Function to count number less // than N which are product of // any two perfect squares function countNumbers( $N ) { return (int)(sqrt( $N )) - 1; } // Driver Code $N = 36; echo countNumbers( $N ); // This code is contributed by akt_mit ?> |
Javascript
<script> // Javascript program to count number less // than N which are product of // any two perfect squares // Function to count number less // than N which are product of // any two perfect squares function countNumbers(N) { return parseInt(Math.sqrt(N), 10) - 1; } let N = 36; document.write(countNumbers(N)); </script> |
Output:
5
Time Complexity: O(log(N)), Auxiliary Space: O(1)
Contact Us