Advertisement
tievo

TP1 Taller

Sep 24th, 2022 (edited)
413
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. -- Tievoli Bruno
  2. -- Riso Santiago
  3. -- Gozzi Juan
  4.  
  5. -- EJERCICIO 1. sonCoprimos
  6. sonCoprimos :: Integer -> Integer -> Bool
  7. sonCoprimos a b = maximoComunDivisor a b == 1
  8.  
  9. -- EJERCICIO 2. es2PseudoPrimo
  10. es2PseudoPrimo :: Integer -> Bool
  11. es2PseudoPrimo n = esAPseudoPrimo 2 n
  12.  
  13. -- EJERCICIO 3. cantidad3PseudoPrimos
  14. cantidad3PseudoPrimos :: Integer -> Integer
  15. cantidad3PseudoPrimos n = contador3PseudoPrimos n 0
  16.  
  17. -- EJERCICIO 4: kesimo2y3Pseudoprimo
  18. kesimo2y3Pseudoprimo :: Integer -> Integer
  19. kesimo2y3Pseudoprimo n = contadorKEsimo2y3Pseudoprimo n 2 1
  20.  
  21. -- EJERCICIO 5: esCarmichael
  22. esCarmichael :: Integer -> Bool
  23. esCarmichael 1 = False
  24. esCarmichael n = contadorCarmichael n (n-1)
  25.  
  26. -----------------------------------------------------------------------
  27. -- Funciones auxiliares
  28. maximoComunDivisor :: Integer -> Integer -> Integer
  29. maximoComunDivisor a 0 = a
  30. maximoComunDivisor a b = maximoComunDivisor b (a `mod` b)
  31.  
  32. menorDivisor :: Integer -> Integer -> Integer
  33. menorDivisor 1 _ = 1
  34. menorDivisor n m | n `mod` m == 0 = m
  35.                  | otherwise = menorDivisor n (m+1)
  36.  
  37. esPrimo :: Integer -> Bool
  38. esPrimo 1 = False
  39. esPrimo n = menorDivisor n 2 == n
  40.  
  41. esAPseudoPrimo :: Integer -> Integer -> Bool
  42. esAPseudoPrimo a n = (a^(n-1)-1) `mod` n == 0 && not (esPrimo n)
  43.  
  44. es3PseudoPrimo :: Integer -> Bool
  45. es3PseudoPrimo n = esAPseudoPrimo 3 n
  46.  
  47. contador3PseudoPrimos :: Integer -> Integer -> Integer
  48. contador3PseudoPrimos 1 m = m
  49. contador3PseudoPrimos n m | es3PseudoPrimo n = contador3PseudoPrimos (n-1) (m+1)
  50.                           | otherwise = contador3PseudoPrimos (n-1) m
  51.                          
  52.  
  53. contadorKEsimo2y3Pseudoprimo :: Integer -> Integer -> Integer -> Integer
  54. contadorKEsimo2y3Pseudoprimo 0 m k = k
  55. contadorKEsimo2y3Pseudoprimo n m k | es2PseudoPrimo m && es3PseudoPrimo m = contadorKEsimo2y3Pseudoprimo (n-1) (m+1) m
  56.                                    | otherwise = contadorKEsimo2y3Pseudoprimo n (m+1) k
  57.                                    
  58.  
  59. contadorCarmichael :: Integer -> Integer -> Bool
  60. contadorCarmichael n 1 = True
  61. contadorCarmichael n m | sonCoprimos m n && not (esAPseudoPrimo m n) = False
  62.                        | otherwise = contadorCarmichael n (m-1)
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement