Conjunto de primos relativos

José A. Alonso

24-05-2024

Dos números enteros positivos son primos relativos si no tienen ningún factor primo en común; es decir, si 1 es su único divisor común. Por ejemplo, 6 y 35 son primos entre sí, pero 6 y 27 no lo son porque ambos son divisibles por 3.

Definir la función

   primosRelativos :: [Int] -> Bool

tal que primosRelativos xs se verifica si los elementos de xs son primos relativos dos a dos. Por ejemplo,

   primosRelativos [6,35]         ==  True
   primosRelativos [6,27]         ==  False
   primosRelativos [2,3,4]        ==  False
   primosRelativos [6,35,11]      ==  True
   primosRelativos [6,35,11,221]  ==  True
   primosRelativos [6,35,11,231]  ==  False

1. Soluciones en Haskell

import Data.Numbers.Primes (primes)
import Test.Hspec (Spec, describe, hspec, it, shouldBe)
import Test.QuickCheck

-- 1ª solución
-- ===========

primosRelativos1 :: [Int] -> Bool
primosRelativos1 []     = True
primosRelativos1 (x:xs) =
  and [sonPrimosRelativos x y | y <- xs] && primosRelativos1 xs

-- (sonPrimosRelativos x y) se verifica si x e y son primos
-- relativos. Por ejemplo,
--    sonPrimosRelativos 6 35  ==  True
--    sonPrimosRelativos 6 27  ==  False
sonPrimosRelativos :: Int -> Int -> Bool
sonPrimosRelativos x y =
  gcd x y == 1

-- 2ª solución
-- ===========

primosRelativos2 :: [Int] -> Bool
primosRelativos2 []     = True
primosRelativos2 (x:xs) =
  all (sonPrimosRelativos x) xs && primosRelativos2 xs

-- Verificación
-- ============

verifica :: IO ()
verifica = hspec spec

specG :: ([Int] -> Bool) -> Spec
specG primosRelativos = do
  it "e1" $
    primosRelativos [6,35]         `shouldBe`  True
  it "e2" $
    primosRelativos [6,27]         `shouldBe`  False
  it "e3" $
    primosRelativos [2,3,4]        `shouldBe`  False
  it "e4" $
    primosRelativos [6,35,11]      `shouldBe`  True
  it "e5" $
    primosRelativos [6,35,11,221]  `shouldBe`  True
  it "e6" $
    primosRelativos [6,35,11,231]  `shouldBe`  False

spec :: Spec
spec = do
  describe "def. 1" $ specG primosRelativos1
  describe "def. 2" $ specG primosRelativos2

-- La verificación es
--    λ> verifica
--    12 examples, 0 failures

-- Comprobación de equivalencia
-- ============================

-- La propiedad es
prop_primosRelativos :: [Positive Int] -> Bool
prop_primosRelativos xs =
  primosRelativos1 ys == primosRelativos2 ys
  where ys = getPositive <$> xs

-- La comprobación es
--    λ> quickCheck prop_primosRelativos
--    +++ OK, passed 100 tests.

-- Comparación de eficiencia
-- =========================

-- La comparación es
--    λ> primosRelativos1 (take 2000 primes)
--    True
--    (1.43 secs, 1,730,437,768 bytes)
--    λ> primosRelativos2 (take 2000 primes)
--    True
--    (0.99 secs, 1,490,445,736 bytes)

2. Soluciones en Python

from math import gcd
from sys import setrecursionlimit
from timeit import Timer, default_timer

from hypothesis import given
from hypothesis import strategies as st
from sympy.ntheory.generate import primerange

setrecursionlimit(10**6)

# 1ª solución
# ===========

# sonPrimosRelativos(x, y) se verifica si x e y son primos
# relativos. Por ejemplo,
#    sonPrimosRelativos(6, 35)  ==  True
#    sonPrimosRelativos(6, 27)  ==  False
def sonPrimosRelativos(x: int, y: int) -> bool:
    return gcd(x, y) == 1

def primosRelativos1(ys: list[int]) -> bool:
    if not ys:
        return True
    x, *xs = ys
    return all(sonPrimosRelativos(x, z) for z in xs) and primosRelativos1(xs)

# 2ª solución
# ===========

def primosRelativos2(ys: list[int]) -> bool:
    if not ys:
        return True
    for y in ys[1:]:
        if gcd(ys[0], y) != 1:
            return False
    return primosRelativos2(ys[1:])

# Verificación
# ============

def test_primosRelativos() -> None:
    for primosRelativos in [primosRelativos1,
                            primosRelativos2]:
        assert primosRelativos([6,35])
        assert not primosRelativos([6,27])
        assert not primosRelativos([2,3,4])
        assert primosRelativos([6,35,11])
        assert primosRelativos([6,35,11,221])
        assert not primosRelativos([6,35,11,231])
    print("Verificado")

# La verificación es
#    >>> test_primosRelativos()
#    Verificado

# Comprobación de equivalencia
# ============================

# La propiedad es
@given(st.lists(st.integers(min_value=1, max_value=1000)))
def test_primosRelativos_equiv(xs: list[int]) -> None:
    assert primosRelativos1(xs) == primosRelativos2(xs)

# La comprobación es
#    >>> test_primosRelativos_equiv()
#    >>>

# Comparación de eficiencia
# =========================

def tiempo(e: str) -> None:
    """Tiempo (en segundos) de evaluar la expresión e."""
    t = Timer(e, "", default_timer, globals()).timeit(1)
    print(f"{t:0.2f} segundos")

# La comparación es
#    >>> tiempo('primosRelativos1(list(primerange(40000)))')
#    2.20 segundos
#    >>> tiempo('primosRelativos2(list(primerange(40000)))')
#    1.82 segundos