¿Qué son los co-primos?
Los números primos son ligeramente diferentes de los números primos. Por un lado, existen en conjuntos de 2 o más números. A diferencia de los números primos, los números primos no pueden existir de forma aislada. Creo que eso es obvio para la mayoría.
Los elementos de un conjunto co-prime pueden o no ser primos.
Por ejemplo: {4, 9, 15}, {5, 16, 11}, etc. son conjuntos primarios de cardinalidad 3.
- Cómo verificar si existe una ruta simple entre los nodos a y b de modo que pase a través del nodo c
- Cómo resolver el problema 144C en Codeforces
- Cómo encontrar la suma de números naturales que suman N usando formularios y funciones en HTML
- Cómo resolver la ordenación rápida utilizando un método no recursivo
- ¿Cuál es la complejidad temporal del algoritmo de búsqueda binaria?
La propiedad importante de los elementos de estos conjuntos es que nunca son divisibles por un número primo común. Solo se pueden dividir comúnmente por 1. Es decir, el máximo común divisor (MCD) del conjunto debe ser igual a 1.
Entonces, básicamente, su algoritmo sería:
boolean isCoprime ({conjunto de enteros}) {
return GCD ({set of integers}) == 1
}
En c ++ STL, tenemos la función __gcd () que toma dos enteros como argumentos y devuelve el gcd. De lo contrario, podemos usar la siguiente implementación del algoritmo euclidiano para calcular el mcd.
int gcd (int a, int b)
{
si (! b) devuelve a;
devuelve mcd (b, a% b);
}
