{"id":8584,"date":"2024-05-24T06:00:57","date_gmt":"2024-05-24T04:00:57","guid":{"rendered":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8584"},"modified":"2024-05-25T19:14:09","modified_gmt":"2024-05-25T17:14:09","slug":"24-may-24","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/24-may-24\/","title":{"rendered":"Conjunto de primos relativos"},"content":{"rendered":"<p>Dos n\u00fameros enteros positivos son <a href=\"http:\/\/bit.ly\/1xgqDTK\">primos relativos<\/a> si no tienen ning\u00fan factor primo en com\u00fan; es decir, 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<p>Definir la funci\u00f3n<\/p>\n<pre lang=\"haskell\">\n   primosRelativos :: [Int] -> Bool\n<\/pre>\n<p>tal que <code>primosRelativos xs<\/code> se verifica si los elementos de <code>xs<\/code> son primos relativos dos a dos. Por ejemplo,<\/p>\n<pre lang=\"haskell\">\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<p><!--more--><\/p>\n<h2>1. Soluciones en Haskell<\/h2>\n<pre lang=\"haskell\">\nimport Data.Numbers.Primes (primes)\nimport Test.Hspec (Spec, describe, hspec, it, shouldBe)\nimport Test.QuickCheck\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nprimosRelativos1 :: [Int] -> Bool\nprimosRelativos1 []     = True\nprimosRelativos1 (x:xs) =\n  and [sonPrimosRelativos x y | y <- xs] &#038;&#038; primosRelativos1 xs\n\n-- (sonPrimosRelativos x y) se verifica si x e y son primos\n-- relativos. Por ejemplo,\n--    sonPrimosRelativos 6 35  ==  True\n--    sonPrimosRelativos 6 27  ==  False\nsonPrimosRelativos :: Int -> Int -> Bool\nsonPrimosRelativos x y =\n  gcd x y == 1\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nprimosRelativos2 :: [Int] -> Bool\nprimosRelativos2 []     = True\nprimosRelativos2 (x:xs) =\n  all (sonPrimosRelativos x) xs && primosRelativos2 xs\n\n-- Verificaci\u00f3n\n-- ============\n\nverifica :: IO ()\nverifica = hspec spec\n\nspecG :: ([Int] -> Bool) -> Spec\nspecG primosRelativos = do\n  it \"e1\" $\n    primosRelativos [6,35]         `shouldBe`  True\n  it \"e2\" $\n    primosRelativos [6,27]         `shouldBe`  False\n  it \"e3\" $\n    primosRelativos [2,3,4]        `shouldBe`  False\n  it \"e4\" $\n    primosRelativos [6,35,11]      `shouldBe`  True\n  it \"e5\" $\n    primosRelativos [6,35,11,221]  `shouldBe`  True\n  it \"e6\" $\n    primosRelativos [6,35,11,231]  `shouldBe`  False\n\nspec :: Spec\nspec = do\n  describe \"def. 1\" $ specG primosRelativos1\n  describe \"def. 2\" $ specG primosRelativos2\n\n-- La verificaci\u00f3n es\n--    \u03bb> verifica\n--    12 examples, 0 failures\n\n-- Comprobaci\u00f3n de equivalencia\n-- ============================\n\n-- La propiedad es\nprop_primosRelativos :: [Positive Int] -> Bool\nprop_primosRelativos xs =\n  primosRelativos1 ys == primosRelativos2 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 2000 primes)\n--    True\n--    (1.43 secs, 1,730,437,768 bytes)\n--    \u03bb> primosRelativos2 (take 2000 primes)\n--    True\n--    (0.99 secs, 1,490,445,736 bytes)\n<\/pre>\n<h2>2. Soluciones en Python<\/h2>\n<pre lang=\"python\">\nfrom math import gcd\nfrom sys import setrecursionlimit\nfrom timeit import Timer, default_timer\n\nfrom hypothesis import given\nfrom hypothesis import strategies as st\nfrom sympy.ntheory.generate import primerange\n\nsetrecursionlimit(10**6)\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\n# sonPrimosRelativos(x, y) se verifica si x e y son primos\n# relativos. Por ejemplo,\n#    sonPrimosRelativos(6, 35)  ==  True\n#    sonPrimosRelativos(6, 27)  ==  False\ndef sonPrimosRelativos(x: int, y: int) -> bool:\n    return gcd(x, y) == 1\n\ndef primosRelativos1(ys: list[int]) -> bool:\n    if not ys:\n        return True\n    x, *xs = ys\n    return all(sonPrimosRelativos(x, z) for z in xs) and primosRelativos1(xs)\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef primosRelativos2(ys: list[int]) -> bool:\n    if not ys:\n        return True\n    for y in ys[1:]:\n        if gcd(ys[0], y) != 1:\n            return False\n    return primosRelativos2(ys[1:])\n\n# Verificaci\u00f3n\n# ============\n\ndef test_primosRelativos() -> None:\n    for primosRelativos in [primosRelativos1,\n                            primosRelativos2]:\n        assert primosRelativos([6,35])\n        assert not primosRelativos([6,27])\n        assert not primosRelativos([2,3,4])\n        assert primosRelativos([6,35,11])\n        assert primosRelativos([6,35,11,221])\n        assert not primosRelativos([6,35,11,231])\n    print(\"Verificado\")\n\n# La verificaci\u00f3n es\n#    >>> test_primosRelativos()\n#    Verificado\n\n# Comprobaci\u00f3n de equivalencia\n# ============================\n\n# La propiedad es\n@given(st.lists(st.integers(min_value=1, max_value=1000)))\ndef test_primosRelativos_equiv(xs: list[int]) -> None:\n    assert primosRelativos1(xs) == primosRelativos2(xs)\n\n# La comprobaci\u00f3n es\n#    >>> test_primosRelativos_equiv()\n#    >>>\n\n# Comparaci\u00f3n de eficiencia\n# =========================\n\ndef tiempo(e: str) -> None:\n    \"\"\"Tiempo (en segundos) de evaluar la expresi\u00f3n e.\"\"\"\n    t = Timer(e, \"\", default_timer, globals()).timeit(1)\n    print(f\"{t:0.2f} segundos\")\n\n# La comparaci\u00f3n es\n#    >>> tiempo('primosRelativos1(list(primerange(40000)))')\n#    2.20 segundos\n#    >>> tiempo('primosRelativos2(list(primerange(40000)))')\n#    1.82 segundos\n<\/pre>\n","protected":false},"excerpt":{"rendered":"<p>Dos n\u00fameros enteros positivos son primos relativos si no tienen ning\u00fan factor primo en com\u00fan; es decir, 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. Definir la funci\u00f3n primosRelativos :: [Int] -> Bool tal&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"default","_kad_post_title":"default","_kad_post_layout":"default","_kad_post_sidebar_id":"","_kad_post_content_style":"default","_kad_post_vertical_padding":"default","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[581],"tags":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8584"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=8584"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8584\/revisions"}],"predecessor-version":[{"id":8585,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8584\/revisions\/8585"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8584"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8584"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8584"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}