Número de pares coprimos de 1 a N con producto igual a N

Dado un número N. La tarea es encontrar el número de pares coprimos (a, b) de 1 a N tales que su producto (a*b) sea igual a N.
Nota : Un par (a, b) es se dice que es coprimo si mcd(a, b) = 1. 
Ejemplos: 
 

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) 

Enfoque: Dado que los elementos del par deben ser coprimos entre sí. Sea un par coprimo (a, b)
Dado, a * b = N .
Por  lo tanto,
a, b <= &\raíz cuadrada(n)$
la idea es ejecutar un ciclo de 1 a  &\raíz cuadrada(N)$y verificar si i y (N/i) son coprimos entre sí o no, y si i*(N/i) = N. En caso afirmativo, cuente esos pares. .
A continuación se muestra la implementación del enfoque anterior: 
 

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>
Producción: 

The co- prime pairs are: 
(3, 40)
(5, 24)
(8, 15)

Number of coprime pairs : 3

 

Publicación traducida automáticamente

Artículo escrito por andrew1234 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *