Cuente números que tienen GCD con N igual al número en sí

Dado un entero positivo N , la tarea es encontrar el número de enteros positivos cuyo MCD con el entero N dado es el número en sí.

Ejemplos:

Entrada: N = 5
Salida: 2
Explicación:
Los siguientes son los números cuyo MCD con N es el número mismo:

1. Número 1: MCD(1, 5) = 1.
2. Número 1: MCD(5, 5) = 5.

Por lo tanto, la cuenta total es 2.

Entrada: N = 10
Salida: 4

Enfoque: El problema dado se puede resolver basándose en la observación de que la condición necesaria para MCD de cualquier número (digamos K ) con N es K si y solo si K es un factor de N . Por lo tanto, la idea es encontrar el número de factores de N . Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos contar como 0 , para contar el número de factores de N.
• Iterar sobre el rango [1, sqrt(N)] y realizar los siguientes pasos:
  • Si el número actual i divide el entero dado N , entonces incremente el conteo en 1 .
  • Si el valor de i y N / i no es el mismo, incremente el conteo en 1 .
• Después de completar los pasos anteriores, imprima el valor de conteo como resultado.

A continuación se muestra la implementación del enfoque anterior:

// C++ program for the above approach
 
#include <bits/stdc++.h>
using namespace std;
 
// Function to count numbers whose
// GCD with N is the number itself
int countNumbers(int N)
{
    // Stores the count of factors of N
    int count = 0;
 
    // Iterate over the range [1, sqrt(N)]
    for (int i = 1; i * i <= N; i++) {
 
        // If i is divisible by i
        if (N % i == 0) {
 
            // Increment count
            count++;
 
            // Avoid counting the
            // same factor twice
            if (N / i != i) {
                count++;
            }
        }
    }
 
    // Return the resultant count
    return count;
}
 
// Driver Code
int main()
{
    int N = 10;
    cout << countNumbers(N);
 
    return 0;
}

// java program for the above approach
import java.io.*;
import java.lang.*;
import java.util.*;
 
public class GFG {
 
    // Function to count numbers whose
    // GCD with N is the number itself
    static int countNumbers(int N)
    {
        // Stores the count of factors of N
        int count = 0;
 
        // Iterate over the range [1, sqrt(N)]
        for (int i = 1; i * i <= N; i++) {
 
            // If i is divisible by i
            if (N % i == 0) {
 
                // Increment count
                count++;
 
                // Avoid counting the
                // same factor twice
                if (N / i != i) {
                    count++;
                }
            }
        }
 
        // Return the resultant count
        return count;
    }
 
    // Driver Code
    public static void main(String[] args)
    {
        int N = 10;
        System.out.println(countNumbers(N));
    }
}
 
// This code is contributed by Kingash.

# Python3 program for the above approach
 
# Function to count numbers whose
# GCD with N is the number itself
def countNumbers(N):
     
    # Stores the count of factors of N
    count = 0
     
    # Iterate over the range [1, sqrt(N)]
    for i in range(1, N + 1):
        if i * i > N:
            break
 
        # If i is divisible by i
        if (N % i == 0):
 
            # Increment count
            count += 1
             
            # Avoid counting the
            # same factor twice
            if (N // i != i):
                count += 1
 
    # Return the resultant count
    return count
 
# Driver Code
if __name__ == '__main__':
     
    N = 10
    print(countNumbers(N))
 
# This code is contributed by mohit kumar 29

// C# program for the above approach
using System;
public class GFG {
 
    // Function to count numbers whose
    // GCD with N is the number itself
    static int countNumbers(int N)
    {
        // Stores the count of factors of N
        int count = 0;
 
        // Iterate over the range [1, sqrt(N)]
        for (int i = 1; i * i <= N; i++) {
 
            // If i is divisible by i
            if (N % i == 0) {
 
                // Increment count
                count++;
 
                // Avoid counting the
                // same factor twice
                if (N / i != i) {
                    count++;
                }
            }
        }
 
        // Return the resultant count
        return count;
    }
 
    // Driver Code
    public static void Main(string[] args)
    {
        int N = 10;
        Console.WriteLine(countNumbers(N));
    }
}
 
// This code is contributed by ukasp.

<script>
 
// Javascript program for the above approach
 
 
// Function to count numbers whose
// GCD with N is the number itself
function countNumbers(N)
{
    // Stores the count of factors of N
    var count = 0;
 
    // Iterate over the range [1, sqrt(N)]
    for (i = 1; i * i <= N; i++) {
 
        // If i is divisible by i
        if (N % i == 0) {
 
            // Increment count
            count++;
 
            // Avoid counting the
            // same factor twice
            if (parseInt(N / i) != i) {
                count++;
            }
        }
    }
 
    // Return the resultant count
    return count;
}
 
// Driver Code
var N = 10;
document.write(countNumbers(N));
 
// This code is contributed by Amit Katiyar
 
</script>

4

Complejidad de Tiempo: O(N ^1/2 )
Espacio Auxiliar: O(1), ya que se ha tomado N espacio extra.