Given a number N. The task is to find the number of co-prime pairs (a, b) from 1 to N such that their product(a*b) is equal to N.
Note: A pair(a, b) is said to be co-prime if gcd(a, b) = 1.
Examples:
Input: N = 120 Output: No. of co-prime pairs = 3 (3, 40) (5, 24) (8, 15) Input: N= 250 Output: No. of co-prime pairs = 3 (2, 125)
Approach: Given that the elements in the pair should be co-prime to each other. Let a co prime pair be (a, b),
Given, a * b = N.
Therefore, 
So the idea is to run a loop from 1 to 
and check whether i and (N/i) are coprime to each other or not and whether, i*(N/i) = N. If yes, then count such pairs.
Below is the implementation of the above approach:
C++
// C++ program to count number of Co-prime pairs// from 1 to N with product equals to N#include <bits/stdc++.h>using namespace std;// Function to count number of Co-prime pairs// from 1 to N with product equals to Nvoid countCoprimePairs(int n){ int count = 0; cout << "The co- prime pairs are: " << endl; // find all the co- prime pairs // Traverse from 2 to sqrt(N) and check // if i, N/i are coprimes for (int i = 2; i <= sqrt(n); i++) { // check if N is divisible by i, // so that the other term in pair i.e. N/i // is integral if (n % i == 0) { // Check if i and N/i are coprime if (__gcd(i, (n / i)) == 1) { // Display the co- prime pairs cout << "(" << i << ", " << (n / i) << ")\n"; count++; } } } cout << "\nNumber of coprime pairs : " << count;}// Driver codeint main(){ int N = 120; countCoprimePairs(N); return 0;} |
Java
// Java program to count number of Co-prime pairs// from 1 to N with product equals to Nimport java.io.*;public class GFG { // Recursive function to return gcd of a and b static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a-b, b); return __gcd(a, b-a); } // Function to count number of Co-prime pairs// from 1 to N with product equals to Nstatic void countCoprimePairs(int n){ int count = 0; System.out.println( "The co- prime pairs are: "); // find all the co- prime pairs // Traverse from 2 to sqrt(N) and check // if i, N/i are coprimes for (int i = 2; i <= Math.sqrt(n); i++) { // check if N is divisible by i, // so that the other term in pair i.e. N/i // is integral if (n % i == 0) { // Check if i and N/i are coprime if (__gcd(i, (n / i)) == 1) { // Display the co- prime pairs System.out.print( "(" +i + ", " + (n / i) + ")\n"); count++; } } } System.out.println("\nNumber of coprime pairs : " + count);}// Driver code public static void main (String[] args) { int N = 120; countCoprimePairs(N); }}// This code is contributed by shs.. |
Python 3
# Python program to count number # of Co-prime pairs from 1 to N # with product equals to N # import everything from math libfrom math import *# Function to count number of # Co-prime pairs from 1 to N# with product equals to N def countCoprimePairs(n) : count = 0 print("The co-prime pairs are: ") # find all the co- prime pairs # Traverse from 2 to sqrt(N) and # check if i, N//i are coprimes for i in range(2, int(sqrt(n)) + 1) : # check if N is divisible by i, # so that the other term in pair # i.e. N/i is integral if n % i == 0 : # Check if i and N/i are coprime if gcd(i, n // i) == 1 : # Display the co- prime pairs print("(", i,",", (n // i),")") count += 1 print("Number of coprime pairs : ", count) # Driver code if __name__ == "__main__" : N = 120 countCoprimePairs(N)# This code is contributed by ANKITRAI1 |
C#
// C# program to count number // of Co-prime pairs from 1 to N // with product equals to Nusing System;class GFG{// Recursive function to// return gcd of a and b static int __gcd(int a, int b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to count number of // Co-prime pairs from 1 to N // with product equals to Nstatic void countCoprimePairs(int n){int count = 0;Console.WriteLine("The co- prime pairs are: ");// find all the co- prime pairs// Traverse from 2 to sqrt(N) and // check if i, N/i are coprimesfor (int i = 2; i <= Math.Sqrt(n); i++) { // check if N is divisible by i, // so that the other term in pair // i.e. N/i is integral if (n % i == 0) { // Check if i and N/i are coprime if (__gcd(i, (n / i)) == 1) { // Display the co- prime pairs Console.WriteLine( "(" + i + ", " + (n / i) + ")\n"); count++; } }}Console.WriteLine("\nNumber of coprime" + " pairs : " + count);}// Driver codepublic static void Main (){ int N = 120; countCoprimePairs(N);}}// This code is contributed by Shashank |
PHP
<?php// PHP program to count number of// Co-prime pairs from 1 to N with // product equals to N// Function to count number of // Co-prime pairs from 1 to N // with product equals to Nfunction gcd($a,$b){ return $b ? gcd($b, $a % $b) : $a;}function countCoprimePairs($n){ $count = 0; echo "The co-prime pairs are: " ."\n"; // find all the co- prime pairs // Traverse from 2 to sqrt(N) and // check if i, N/i are coprimes for ($i = 2; $i <= sqrt($n); $i++) { // check if N is divisible by i, // so that the other term in pair // i.e. N/i is integral if ($n % $i == 0) { // Check if i and N/i are coprime if (gcd($i, ($n / $i)) == 1) { // Display the co- prime pairs echo "(" .$i . ", " . ($n / $i) .")\n"; $count++; } } } echo "\nNumber of coprime pairs : " . $count;}// Driver code$N = 120;countCoprimePairs($N);// This code is contributed// by ChitraNayal?> |
Javascript
<script>// Javascript program to count number of Co-prime pairs// from 1 to N with product equals to N// Recursive function to// return gcd of a and b function __gcd(a, b) { // Everything divides 0 if (a == 0) return b; if (b == 0) return a; // base case if (a == b) return a; // a is greater if (a > b) return __gcd(a - b, b); return __gcd(a, b - a); } // Function to count number of Co-prime pairs// from 1 to N with product equals to Nfunction countCoprimePairs(n){ var count = 0; document.write( "The co- prime pairs are: " + "<br>"); // find all the co- prime pairs // Traverse from 2 to sqrt(N) and check // if i, N/i are coprimes for (var i = 2; i <= Math.sqrt(n); i++) { // check if N is divisible by i, // so that the other term in pair i.e. N/i // is integral if (n % i == 0) { // Check if i and N/i are coprime if (__gcd(i, parseInt(n / i)) == 1) { // Display the co- prime pairs document.write( "(" + i + ", " + parseInt(n / i) + ")<br>"); count++; } } } document.write( "<br>Number of coprime pairs : " + count);}// Driver codevar N = 120;countCoprimePairs(N);</script> |
Output:
The co- prime pairs are: (3, 40) (5, 24) (8, 15) Number of coprime pairs : 3
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
