Recuento de números hasta N que tienen al menos un factor primo común con N

Dado un número entero N , la tarea es contar el número de números enteros del rango [1, N] que tienen al menos un factor primo común con N distinto de 1 .

Ejemplos:

Entrada: N = 5
Salida: 1
Explicación: 
Dado que 5 es primo. Por lo tanto, no hay otro número que sea a lo sumo N, que tenga al menos un factor común con N excepto el propio N. Por lo tanto, la cuenta es 1.

Entrada: N = 12
Salida: 8

Enfoque ingenuo: el enfoque más simple para resolver el problema dado es iterar a través de todos los números en el rango [1, N] , y para cada elemento, si el GCD de cada número con N es mayor que 1 , entonces incrementa el conteo. De lo contrario, busque el siguiente número. Después de comprobar todos los números, imprimimos el recuento total obtenido.

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 all the numbers
// in the range [1, N] having common
// factor with N other than 1
int countNumbers(int N)
{
    // Stores the count of numbers
    // having more than 1 factor with N
    int count = 0;
 
    // Iterate over the range [1, N]
    for (int i = 1; i <= N; i++) {
 
        // If gcd is not 1 then
        // increment the count
        if (__gcd(i, N) != 1)
            count++;
    }
 
    // Print the resultant count
    cout << count;
}
 
// Driver Code
int main()
{
    int N = 5;
    countNumbers(N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
 
class GFG{
 
// Function to count all the numbers
// in the range [1, N] having common
// factor with N other than 1
static void countNumbers(int N)
{
     
    // Stores the count of numbers
    // having more than 1 factor with N
    int count = 0;
 
    // Iterate over the range [1, N]
    for(int i = 1; i <= N; i++)
    {
         
        // If gcd is not 1 then
        // increment the count
        if (__gcd(i, N) != 1)
            count++;
    }
 
    // Print the resultant count
    System.out.print(count);
}
 
static int __gcd(int a, int b)
{
    return b == 0 ? a : __gcd(b, a % b);
}
 
// Driver Code
public static void main(String[] args)
{
    int N = 5;
    countNumbers(N);
}
}
 
// This code is contributed by shikhasingrajput

# Python 3 program for the above approach
import math
 
# Function to count all the numbers
# in the range [1, N] having common
# factor with N other than 1
def countNumbers(N):
 
    # Stores the count of numbers
    # having more than 1 factor with N
    count = 0
 
    # Iterate over the range [1, N]
    for i in range(1, N + 1):
 
        # If gcd is not 1 then
        # increment the count
        if (math.gcd(i, N) != 1):
            count += 1
 
    # Print the resultant count
    print(count)
 
 
# Driver Code
if __name__ == "__main__":
 
    N = 5
    countNumbers(N)
 
    # This code is contributed by ukasp.

// C# program for the above approach
using System;
 
public class GFG{
 
// Function to count all the numbers
// in the range [1, N] having common
// factor with N other than 1
static void countNumbers(int N)
{
     
    // Stores the count of numbers
    // having more than 1 factor with N
    int count = 0;
 
    // Iterate over the range [1, N]
    for(int i = 1; i <= N; i++)
    {
         
        // If gcd is not 1 then
        // increment the count
        if (__gcd(i, N) != 1)
            count++;
    }
 
    // Print the resultant count
    Console.Write(count);
}
 
static int __gcd(int a, int b)
{
    return b == 0 ? a : __gcd(b, a % b);
}
 
// Driver Code
public static void Main(String[] args)
{
    int N = 5;
    countNumbers(N);
}
}
 
  
 
// This code is contributed by 29AjayKumar

<script>
// javascript program for the above approach
 
// Function to count all the numbers
// in the range [1, N] having common
// factor with N other than 1
function countNumbers(N)
{
     
    // Stores the count of numbers
    // having more than 1 factor with N
    var count = 0;
 
    // Iterate over the range [1, N]
    for(var i = 1; i <= N; i++)
    {
         
        // If gcd is not 1 then
        // increment the count
        if (__gcd(i, N) != 1)
            count++;
    }
 
    // Print the resultant count
    document.write(count);
}
 
function __gcd(a , b)
{
    return b == 0 ? a : __gcd(b, a % b);
}
 
// Driver Code
var N = 5;
countNumbers(N);
 
// This code is contributed by 29AjayKumar
</script>

1

Complejidad de Tiempo: O(N*log N)
Espacio Auxiliar: O(1), ya que no se ha tomado espacio extra.

Enfoque eficiente: el enfoque anterior también se puede optimizar mediante el uso de la función totient de Euler, que proporciona el recuento de números menores que N que no tienen un factor primo común con N. Siga los pasos a continuación para resolver el problema:

• Inicialice una variable, digamos contar , que almacena los números que tienen factores primos comunes distintos de 1 .
• Defina una función, phi() para calcular el valor de la función totient de Euler que representa el recuento de números enteros menores que N que no tienen factor común con N .
• Después de completar los pasos anteriores, imprima el valor de (N – phi(N) como el conteo resultante.

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 calculate the value of
// Euler's totient function
int phi(int N)
{
    // Initialize result with N
    int result = N;
 
    // Find all prime factors of N
    // and subtract their multiples
    for (int p = 2; p * p <= N; ++p) {
 
        // Check if p is a prime factor
        if (N % p == 0) {
 
            // If found to be true,
            // then update N and result
            while (N % p == 0)
                N /= p;
 
            result -= result / p;
        }
    }
 
    // If N has a prime factor greater
    // than sqrt(N), then there can be
    // at-most one such prime factor
    if (N > 1)
        result -= result / N;
 
    return result;
}
 
// Function to count all the numbers
// in the range [1, N] having common
// factor with N other than 1
int countNumbers(int N)
{
    // Stores the resultant count
    int count = N - phi(N);
 
    // Print the count
    cout << count;
}
 
// Driver Code
int main()
{
    int N = 5;
    countNumbers(N);
 
    return 0;
}

// Java program for the above approach
import java.util.*;
class GFG
{
     
 // Function to calculate the value of
// Euler's totient function
static int phi(int N)
{
   
    // Initialize result with N
    int result = N;
 
    // Find all prime factors of N
    // and subtract their multiples
    for (int p = 2; p * p <= N; ++p)
    {
 
        // Check if p is a prime factor
        if (N % p == 0) {
 
            // If found to be true,
            // then update N and result
            while (N % p == 0)
                N /= p;
 
            result -= result / p;
        }
    }
 
    // If N has a prime factor greater
    // than sqrt(N), then there can be
    // at-most one such prime factor
    if (N > 1)
        result -= result / N;
 
    return result;
}
 
// Function to count all the numbers
// in the range [1, N] having common
// factor with N other than 1
static void countNumbers(int N)
{
   
    // Stores the resultant count
    int count = N - phi(N);
 
    // Print the count
   System.out.print(count);
}
 
  // Driver code
public static void main (String[] args)
{
     int N = 5;
    countNumbers(N);
}
}
 
// This code is contributed by offbeat.

# Python3 program for the above approach
 
# Function to calculate the value of
# Euler's totient function
def phi(N):
     
    # Initialize result with N
    result = N
     
    # Find all prime factors of N
    # and subtract their multiples
    for p in range(2, int(pow(N, 1 / 2)) + 1):
         
        # Check if p is a prime factor
        if (N % p == 0):
             
            # If found to be true,
            # then update N and result
            while (N % p == 0):
                N = N / p
 
            result -= result // p
         
    # If N has a prime factor greater
    # than sqrt(N), then there can be
    # at-most one such prime factor
    if (N > 1):
        result -= result // N
 
    return result
 
# Function to count all the numbers
# in the range [1, N] having common
# factor with N other than 1
def countNumbers(N):
     
    # Stores the resultant count
    count = N - phi(N)
 
    # Print the count
    print(count)
 
# Driver Code
N = 5
 
countNumbers(N)
 
# This code is contributed by SoumikMondal

// C# program for the above approach
using System;
 
public class GFG
{
     
 // Function to calculate the value of
// Euler's totient function
static int phi(int N)
{
   
    // Initialize result with N
    int result = N;
 
    // Find all prime factors of N
    // and subtract their multiples
    for (int p = 2; p * p <= N; ++p)
    {
 
        // Check if p is a prime factor
        if (N % p == 0) {
 
            // If found to be true,
            // then update N and result
            while (N % p == 0)
                N /= p;
 
            result -= result / p;
        }
    }
 
    // If N has a prime factor greater
    // than sqrt(N), then there can be
    // at-most one such prime factor
    if (N > 1)
        result -= result / N;
 
    return result;
}
 
// Function to count all the numbers
// in the range [1, N] having common
// factor with N other than 1
static void countNumbers(int N)
{
   
    // Stores the resultant count
    int count = N - phi(N);
 
    // Print the count
   Console.Write(count);
}
 
  // Driver code
public static void Main(String[] args)
{
     int N = 5;
    countNumbers(N);
}
}
 
// This code contributed by shikhasingrajput

<script>
 
// Javascript implementation
// for the above approach
 
// Function to calculate the value of
// Euler's totient function
function phi(N)
{
    
    // Initialize result with N
    let result = N;
  
    // Find all prime factors of N
    // and subtract their multiples
    for (let p = 2; p * p <= N; ++p)
    {
  
        // Check if p is a prime factor
        if (N % p == 0) {
  
            // If found to be true,
            // then update N and result
            while (N % p == 0)
                N /= p;
  
            result -= result / p;
        }
    }
  
    // If N has a prime factor greater
    // than sqrt(N), then there can be
    // at-most one such prime factor
    if (N > 1)
        result -= result / N;
  
    return result;
}
  
// Function to count all the numbers
// in the range [1, N] having common
// factor with N other than 1
function countNumbers(N)
{
    
    // Stores the resultant count
    let count = N - phi(N);
  
    // Print the count
       document.write(count);
}
 
// Driver Code
     
    let N = 5;
    countNumbers(N);
 
// This code is contributed by susmitakundugoaldanga.
</script>

1

Complejidad de tiempo: O(sqrt(N))
Espacio auxiliar: O(1)