{"id":6848,"date":"2022-03-30T06:00:42","date_gmt":"2022-03-30T04:00:42","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=6848"},"modified":"2022-04-06T07:54:30","modified_gmt":"2022-04-06T05:54:30","slug":"conjunto-de-primos-relativos","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/conjunto-de-primos-relativos\/","title":{"rendered":"Conjunto de primos relativos"},"content":{"rendered":"

Dos n\u00fameros enteros positivos son primos relativos<\/a> si no tienen ning\u00fan factor primo en com\u00fan; es decit, si 1 es su \u00fanico divisor com\u00fan. Por ejemplo, 6 y 35 son primos entre s\u00ed, pero 6 y 27 no lo son porque ambos son divisibles por 3.<\/p>\n

Definir la funci\u00f3n<\/p>\n

\n   primosRelativos :: [Int] -> Bool\n<\/pre>\n
tal que (primosRelativos xs)<\/code> se verifica si los elementos de xs<\/code> son primos relativos dos a dos. Por ejemplo,<\/p>\n
\n   primosRelativos [6,35]         ==  True\n   primosRelativos [6,27]         ==  False\n   primosRelativos [2,3,4]        ==  False\n   primosRelativos [6,35,11]      ==  True\n   primosRelativos [6,35,11,221]  ==  True\n   primosRelativos [6,35,11,231]  ==  False\n<\/pre>\n
Soluciones<\/h4>\n
\nimport Test.QuickCheck\nimport Data.List (delete, intersect)\nimport Data.Numbers.Primes (primeFactors, primes)\nimport qualified Data.Set as S (disjoint, fromList)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nprimosRelativos1 :: [Int] -> Bool\nprimosRelativos1 []     = True\nprimosRelativos1 (x:xs) =\n  and [sonPrimosRelativos1 x y | y <- xs] && primosRelativos1 xs\n\n-- (sonPrimosRelativos x y) se verifica si x e y son primos\n-- relativos. Por ejemplo,\n--    sonPrimosRelativos1 6 35  ==  True\n--    sonPrimosRelativos1 6 27  ==  False\nsonPrimosRelativos1 :: Int -> Int -> Bool\nsonPrimosRelativos1 x y =\n  null (divisoresPrimos x `intersect` divisoresPrimos y)\n\n-- (divisoresPrimos x) es la lista de los divisores primos de x. Por\n-- ejemplo,\n--    divisoresPrimos 600  ==  [2,2,2,3,5,5]\ndivisoresPrimos :: Int -> [Int]\ndivisoresPrimos 1 = []\ndivisoresPrimos x =\n  y : divisoresPrimos (x `div` y)\n  where y = menorDivisorPrimo x\n\n-- (menorDivisorPrimo x) es el menor divisor primo de x. Por ejemplo,\n--    menorDivisorPrimo 15  ==  3\n--    menorDivisorPrimo 11  ==  11\nmenorDivisorPrimo :: Int -> Int\nmenorDivisorPrimo x =\n  head [y | y <- [2..], x `mod` y == 0]\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nprimosRelativos2 :: [Int] -> Bool\nprimosRelativos2 []     = True\nprimosRelativos2 (x:xs) =\n  all (sonPrimosRelativos1 x) xs && primosRelativos2 xs\n\n-- 3\u00aa soluci\u00f3n\n-- ===========\n\nprimosRelativos3 :: [Int] -> Bool\nprimosRelativos3 []     = True\nprimosRelativos3 (x:xs) =\n  all (sonPrimosRelativos2 x) xs && primosRelativos3 xs\n\nsonPrimosRelativos2 :: Int -> Int -> Bool\nsonPrimosRelativos2 x y =\n  null (primeFactors x `intersect` primeFactors y)\n\n-- 4\u00aa soluci\u00f3n\n-- ===========\n\nprimosRelativos4 :: [Int] -> Bool\nprimosRelativos4 []     = True\nprimosRelativos4 (x:xs) =\n  all (sonPrimosRelativos3 x) xs && primosRelativos4 xs\n\nsonPrimosRelativos3 :: Int -> Int -> Bool\nsonPrimosRelativos3 x y =\n  S.fromList (primeFactors x) `S.disjoint` S.fromList (primeFactors y)\n\n-- 5\u00aa soluci\u00f3n\n-- ===========\n\nprimosRelativos5 :: [Int] -> Bool\nprimosRelativos5 []     = True\nprimosRelativos5 (x:xs) =\n  all (sonPrimosRelativos5 x) xs && primosRelativos5 xs\n\nsonPrimosRelativos5 :: Int -> Int -> Bool\nsonPrimosRelativos5 x y =\n  gcd x y == 1\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_primosRelativos :: [Positive Int] -> Bool\nprop_primosRelativos xs =\n  all (== primosRelativos1 ys)\n      [primosRelativos2 ys,\n       primosRelativos3 ys,\n       primosRelativos4 ys,\n       primosRelativos5 ys]\n  where ys = getPositive <$> xs\n\n-- La comprobaci\u00f3n es\n--    \u03bb> quickCheck prop_primosRelativos\n--    +++ OK, passed 100 tests.\n\n-- Comparaci\u00f3n de eficiencia\n-- =========================\n\n-- La comparaci\u00f3n es\n--    \u03bb> primosRelativos1 (take 120 primes)\n--    True\n--    (1.92 secs, 869,909,416 bytes)\n--    \u03bb> primosRelativos2 (take 120 primes)\n--    True\n--    (1.99 secs, 869,045,656 bytes)\n--    \u03bb> primosRelativos3 (take 120 primes)\n--    True\n--    (0.09 secs, 221,183,200 bytes)\n--\n--    \u03bb> primosRelativos3 (take 600 primes)\n--    True\n--    (2.62 secs, 11,196,690,856 bytes)\n--    \u03bb> primosRelativos4 (take 600 primes)\n--    True\n--    (2.66 secs, 11,190,940,456 bytes)\n--    \u03bb> primosRelativos5 (take 600 primes)\n--    True\n--    (0.14 secs, 123,673,648 bytes)\n<\/pre>\n
El c\u00f3digo se encuentra en GitHub<\/a>.<\/p>\n
La elaboraci\u00f3n de las soluciones se describe en el siguiente v\u00eddeo<\/p>\n