Primos equidistantes
Definir la función
|
1 |
primosEquidistantes :: Integer -> [(Integer,Integer)] |
tal que primosEquidistantes k es la lista de los pares de primos cuya diferencia es k. Por ejemplo,
|
1 2 3 4 5 |
take 3 (primosEquidistantes 2) == [(3,5),(5,7),(11,13)] take 3 (primosEquidistantes 4) == [(7,11),(13,17),(19,23)] take 3 (primosEquidistantes 6) == [(23,29),(31,37),(47,53)] take 3 (primosEquidistantes 8) == [(89,97),(359,367),(389,397)] primosEquidistantes 4 !! (10^5) == (18467047,18467051) |
1. Soluciones en Haskell
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 |
module Primos_equidistantes where import Data.Numbers.Primes (primes) import Test.Hspec (Spec, describe, hspec, it, shouldBe) -- 1ª solución -- =========== primosEquidistantes1 :: Integer -> [(Integer,Integer)] primosEquidistantes1 k = aux primos where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps) | otherwise = aux (y:ps) -- (primo x) se verifica si x es primo. Por ejemplo, -- primo 7 == True -- primo 8 == False primo :: Integer -> Bool primo x = [y | y <- [1..x], x `rem` y == 0] == [1,x] -- primos es la lista de los números primos. Por ejemplo, -- take 10 primos == [2,3,5,7,11,13,17,19,23,29] primos :: [Integer] primos = 2 : [x | x <- [3,5..], primo x] -- 2ª solución -- =========== primosEquidistantes2 :: Integer -> [(Integer,Integer)] primosEquidistantes2 k = aux primos2 where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps) | otherwise = aux (y:ps) primos2 :: [Integer] primos2 = criba [2..] where criba (p:ps) = p : criba [n | n <- ps, mod n p /= 0] -- 3ª solución -- =========== primosEquidistantes3 :: Integer -> [(Integer,Integer)] primosEquidistantes3 k = [(x,y) | (x,y) <- zip primos2 (tail primos2) , y - x == k] -- 4ª solución -- =========== primosEquidistantes4 :: Integer -> [(Integer,Integer)] primosEquidistantes4 k = aux primes where aux (x:y:ps) | y - x == k = (x,y) : aux (y:ps) | otherwise = aux (y:ps) -- 5ª solución -- =========== primosEquidistantes5 :: Integer -> [(Integer,Integer)] primosEquidistantes5 k = [(x,y) | (x,y) <- zip primes (tail primes) , y - x == k] -- Verificación -- ============ verifica :: IO () verifica = hspec spec specG :: (Integer -> [(Integer,Integer)]) -> Spec specG primosEquidistantes = do it "e1" $ take 3 (primosEquidistantes 2) `shouldBe` [(3,5),(5,7),(11,13)] it "e2" $ take 3 (primosEquidistantes 4) `shouldBe` [(7,11),(13,17),(19,23)] it "e3" $ take 3 (primosEquidistantes 6) `shouldBe` [(23,29),(31,37),(47,53)] it "e4" $ take 3 (primosEquidistantes 8) `shouldBe` [(89,97),(359,367),(389,397)] spec :: Spec spec = do describe "def. 1" $ specG primosEquidistantes1 describe "def. 2" $ specG primosEquidistantes2 describe "def. 3" $ specG primosEquidistantes3 describe "def. 4" $ specG primosEquidistantes4 describe "def. 5" $ specG primosEquidistantes5 -- La verificación es -- λ> verifica -- 20 examples, 0 failures -- Comprobación de equivalencia -- ============================ -- La propiedad es prop_primosEquidistantes :: Int -> Integer -> Bool prop_primosEquidistantes n k = all (== take n (primosEquidistantes1 k)) [take n (f k) | f <- [primosEquidistantes2, primosEquidistantes3, primosEquidistantes4, primosEquidistantes5]] -- La comprobación es -- λ> prop_primosEquidistantes 100 4 -- True -- Comparación de eficiencia -- ========================= -- La comparación es -- λ> primosEquidistantes1 4 !! 200 -- (9829,9833) -- (2.60 secs, 1,126,458,272 bytes) -- λ> primosEquidistantes2 4 !! 200 -- (9829,9833) -- (0.44 secs, 249,622,048 bytes) -- λ> primosEquidistantes3 4 !! 200 -- (9829,9833) -- (0.36 secs, 207,549,592 bytes) -- λ> primosEquidistantes4 4 !! 200 -- (9829,9833) -- (0.02 secs, 4,012,848 bytes) -- λ> primosEquidistantes5 4 !! 200 -- (9829,9833) -- (0.01 secs, 7,085,072 bytes) -- -- λ> primosEquidistantes2 4 !! 600 -- (41617,41621) -- (5.67 secs, 3,340,313,480 bytes) -- λ> primosEquidistantes3 4 !! 600 -- (41617,41621) -- (5.43 secs, 3,090,994,096 bytes) -- λ> primosEquidistantes4 4 !! 600 -- (41617,41621) -- (0.03 secs, 15,465,824 bytes) -- λ> primosEquidistantes5 4 !! 600 -- (41617,41621) -- (0.04 secs, 28,858,232 bytes) -- -- λ> primosEquidistantes4 4 !! (10^5) -- (18467047,18467051) -- (3.99 secs, 9,565,715,488 bytes) -- λ> primosEquidistantes5 4 !! (10^5) -- (18467047,18467051) -- (7.95 secs, 18,712,469,144 bytes) |
2. Soluciones en Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 |
from itertools import chain, count, islice, tee from timeit import Timer, default_timer from typing import Iterator from sympy import isprime # 1ª solución # =========== # primo(x) se verifica si x es primo. Por ejemplo, # primo(7) == True # primo(8) == False def primo(x: int) -> bool: return [y for y in range(1,x+1) if x % y == 0] == [1,x] # primos() es la lista de los números primos. Por ejemplo, # >>> list(islice(primos(), 10)) # [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] def primos() -> Iterator[int]: return chain([2], (x for x in count(3, 2) if primo(x))) def primosEquidistantes1(k: int) -> Iterator[tuple[int,int]]: a, b = tee(primos()) next(b, None) return ((x,y) for (x,y) in zip(a, b) if y - x == k) # 2ª solución # =========== def primos2() -> Iterator[int]: return (n for n in count() if isprime(n)) def primosEquidistantes2(k: int) -> Iterator[tuple[int,int]]: a, b = tee(primos2()) next(b, None) return ((x,y) for (x,y) in zip(a, b) if y - x == k) # Verificación # ============ def test_primosEquidestantes() -> None: for primosEquidistantes in [primosEquidistantes1, primosEquidistantes2]: assert list(islice(primosEquidistantes(2), 3)) == \ [(3, 5), (5, 7), (11, 13)] assert list(islice(primosEquidistantes(4), 3)) == \ [(7, 11), (13, 17), (19, 23)] assert list(islice(primosEquidistantes(6), 3)) == \ [(23, 29), (31, 37), (47, 53)] assert list(islice(primosEquidistantes(8), 3)) == \ [(89, 97), (359, 367), (389, 397)] print("Verificado") # La verificación es # >>> test_primosEquidestantes() # Verificado # Comprobación de equivalencia # ============================ # La propiedad es def primosEquidistantes_equiv(n: int, k: int) -> bool: return list(islice(primosEquidistantes1(k), n)) == \ list(islice(primosEquidistantes2(k), n)) # La comprobación es # >>> primosEquidistantes_equiv(100, 4) # True # 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('list(islice(primosEquidistantes1(4), 300))') # 3.19 segundos # >>> tiempo('list(islice(primosEquidistantes2(4), 300))') # 0.01 segundos |