Dados dos enteros y , la tarea es encontrar los divisores primos comunes de estos números.
Ejemplos:
Entrada: A = 6, B = 12
Salida: 2 3
2 y 3 son los únicos divisores primos comunes de 6 y 12
Entrada: A = 4, B = 8
Salida: 2
Enfoque ingenuo: itere de 1 a min (A, B) y verifique si i es primo y un factor de A y B , si es así, muestre el número.
El enfoque eficiente es hacer lo siguiente:
- Encuentra el máximo común divisor (mcd) de los números dados.
- Encuentra los factores primos del GCD.
Enfoque eficiente para consultas múltiples: la solución anterior se puede optimizar aún más si hay consultas múltiples para factores comunes. La idea se basa en la factorización prima usando Sieve O(log n) para consultas múltiples .
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach #include <bits/stdc++.h> using namespace std; #define MAXN 100001 bool prime[MAXN]; void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. memset(prime, true, sizeof(prime)); // 0 and 1 are not prime numbers prime[0] = false; prime[1] = false; for (int p = 2; p * p <= MAXN; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p as non-prime for (int i = p * p; i <= MAXN; i += p) prime[i] = false; } } } // Find the common prime divisors void common_prime(int a, int b) { // Get the GCD of the given numbers int gcd = __gcd(a, b); // Find the prime divisors of the gcd for (int i = 2; i <= (gcd); i++) { // If i is prime and a divisor of gcd if (prime[i] && gcd % i == 0) { cout << i << " "; } } } // Driver code int main() { // Create the Sieve SieveOfEratosthenes(); int a = 6, b = 12; common_prime(a, b); return 0; }
Java
//Java implementation of above approach class GFG { static final int MAXN = 100001; static boolean prime[] = new boolean[MAXN]; static void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. for(int i = 0;i<prime.length;i++) prime[i]=true; // 0 and 1 are not prime numbers prime[0] = false; prime[1] = false; for (int p = 2; p * p < MAXN; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p as non-prime for (int i = p * p; i < MAXN; i += p) prime[i] = false; } } } // Find the common prime divisors static void common_prime(int a, int b) { // Get the GCD of the given numbers int gcd = (int) __gcd(a, b); // Find the prime divisors of the gcd for (int i = 2; i <= (gcd); i++) { // If i is prime and a divisor of gcd if (prime[i] && gcd % i == 0) { System.out.print(i + " "); } } } static long __gcd(long a, long b) { if (a == 0) return b; return __gcd(b % a, a); } // Driver code public static void main(String[] args) { // Create the Sieve SieveOfEratosthenes(); int a = 6, b = 12; common_prime(a, b); } } /*This code is contributed by 29AjayKumar*/
Python3
# Python implementation of above approach from math import gcd, sqrt # Create a boolean array "prime[0..n]" # and initialize all entries it as true. # A value in prime[i] will finally be # false if i is Not a prime, else true. prime = [True] * 100001 def SieveOfEratosthenes() : # 0 and 1 are not prime numbers prime[0] = False prime[1] = False for p in range(2, int(sqrt(100001)) + 1) : # If prime[p] is not changed, # then it is a prime if prime[p] == True : # Update all multiples of # p as non-prime for i in range(p**2, 100001, p) : prime[i] = False # Find the common prime divisors def common_prime(a, b) : # Get the GCD of the given numbers __gcd = gcd(a, b) # Find the prime divisors of the gcd for i in range(2, __gcd + 1) : # If i is prime and a divisor of gcd if prime[i] and __gcd % i == 0 : print(i, end = " ") # Driver code if __name__ == "__main__" : # Create the Sieve SieveOfEratosthenes() a, b = 6, 12 common_prime(a, b) # This code is contributed by ANKITRAI1
C#
//C# implementation of above approach using System; public class GFG { static bool []prime = new bool[100001]; static void SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. for(int i = 0;i<prime.Length;i++) prime[i]=true; // 0 and 1 are not prime numbers prime[0] = false; prime[1] = false; for (int p = 2; p * p < 100001; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p as non-prime for (int i = p * p; i < 100001; i += p) prime[i] = false; } } } // Find the common prime divisors static void common_prime(int a, int b) { // Get the GCD of the given numbers int gcd = (int) __gcd(a, b); // Find the prime divisors of the gcd for (int i = 2; i <= (gcd); i++) { // If i is prime and a divisor of gcd if (prime[i] && gcd % i == 0) { Console.Write(i + " "); } } } static long __gcd(long a, long b) { if (a == 0) return b; return __gcd(b % a, a); } // Driver code public static void Main() { // Create the Sieve SieveOfEratosthenes(); int a = 6, b = 12; common_prime(a, b); } } /*This code is contributed by 29AjayKumar*/
Javascript
<script> // Javascript program to implement the above approach MAXN = parseInt(100001); prime = new Array(MAXN); function __gcd(a, b) { if (a == 0) return b; return __gcd(b % a, a); } function SieveOfEratosthenes() { // Create a boolean array "prime[0..n]" and initialize // all entries it as true. A value in prime[i] will // finally be false if i is Not a prime, else true. prime.fill(true); // 0 and 1 are not prime numbers prime[0] = false; prime[1] = false; for (var p = 2; p * p <= MAXN; p++) { // If prime[p] is not changed, then it is a prime if (prime[p] == true) { // Update all multiples of p as non-prime for (var i = p * p; i <= MAXN; i += p) prime[i] = false; } } } // Find the common prime divisors function common_prime( a, b) { // Get the GCD of the given numbers var gcd = __gcd(a, b); // Find the prime divisors of the gcd for (var i = 2; i <= (gcd); i++) { // If i is prime and a divisor of gcd if (prime[i] && gcd % i == 0) { document.write( i + " "); } } } SieveOfEratosthenes(); var a = 6, b = 12; common_prime(a, b); //This code is contributed by SoumikModnal </script>
2 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