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++
// 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
// 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
Python3
# 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#
// 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
Javascript
<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++
// 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
// 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
# 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#
// 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
Javascript
<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)
Publicación traducida automáticamente
Artículo escrito por shekabhi1208 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA