Number of Co-prime pairs from 1 to N with product equals to N

0 0 6 minutes read

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,
$a, b <= &\sqrt(n)$$
So the idea is to run a loop from 1 to $&\sqrt(N)$$ 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 N
void 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 code
int 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 N
import 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 N
static 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 lib
from 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 N
using 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 N
static 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 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
            Console.WriteLine( "(" + i + ", " + 
                              (n / i) + ")\n");
            count++;
        }
    }
}
 
Console.WriteLine("\nNumber of coprime" + 
                    " pairs : " + count);
}
 
// Driver code
public 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 N
function 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 N
function 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 code
var 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 zambiatek!