libreDeCuadrados :: Integer -> Bool

   libreDeCuadrados 70  ==  True
   libreDeCuadrados 40  ==  False
   libreDeCuadrados (product (take 30000 primes))  ==  True

import Data.List (nub)
import Data.Numbers.Primes (primeFactors, primes)
import Test.QuickCheck

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

libreDeCuadrados1 :: Integer -> Bool
libreDeCuadrados1 n =
  null [x | x <- [2..n], rem n (x^2) == 0]

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

libreDeCuadrados2 :: Integer -> Bool
libreDeCuadrados2 x =
  x == product (divisoresPrimos2 x)

-- (divisoresPrimos x) es la lista de los divisores primos de x. Por
-- ejemplo,
--    divisoresPrimos 40 == [2,5]
--    divisoresPrimos 70 == [2,5,7]
divisoresPrimos2 :: Integer -> [Integer]
divisoresPrimos2 x = [n | n <- divisores2 x, primo2 n]

-- (divisores n) es la lista de los divisores del número n. Por ejemplo,
--    divisores 25  ==  [1,5,25]
--    divisores 30  ==  [1,2,3,5,6,10,15,30]
divisores2 :: Integer -> [Integer]
divisores2 n = [x | x <- [1..n], n `mod` x == 0]

-- (primo n) se verifica si n es primo. Por ejemplo,
--    primo 30  == False
--    primo 31  == True
primo2 :: Integer -> Bool
primo2 n = divisores2 n == [1, n]

-- 3ª solución
-- ===========

libreDeCuadrados3 :: Integer -> Bool
libreDeCuadrados3 n
  | even n = n `mod` 4 /= 0 && libreDeCuadrados3 (n `div` 2)
  | otherwise = aux n [3,5..n]
  where aux 1 _  = True
        aux _ [] = True
        aux m (x:xs)
          | m `mod` x == 0 = m `mod` (x^2) /= 0 && aux (m `div` x) xs
          | otherwise      = aux m xs

-- 4ª solución
-- ===========

libreDeCuadrados4 :: Integer -> Bool
libreDeCuadrados4 x =
  x == product (divisoresPrimos4 x)

divisoresPrimos4 :: Integer -> [Integer]
divisoresPrimos4 = nub . primeFactors

-- 5ª solución
-- ===========

libreDeCuadrados5 :: Integer -> Bool
libreDeCuadrados5 =
  sinRepetidos . primeFactors

-- (sinRepetidos xs) se verifica si xs no tiene elementos repetidos. Por
-- ejemplo,
--    sinRepetidos [3,2,5]  ==  True
--    sinRepetidos [3,2,5,2]  ==  False
sinRepetidos :: [Integer] -> Bool
sinRepetidos xs =
  nub xs == xs

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

-- La propiedad es
prop_libreDeCuadrados :: Integer -> Property
prop_libreDeCuadrados x =
  x > 1 ==>
  all (== libreDeCuadrados1 x)
      [libreDeCuadrados2 x,
       libreDeCuadrados3 x,
       libreDeCuadrados4 x,
       libreDeCuadrados5 x]

-- La comprobación es
--    λ> quickCheck prop_libreDeCuadrados
--    +++ OK, passed 100 tests; 165 discarded.

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

-- La comparación es
--    λ> libreDeCuadrados1 9699690
--    True
--    (8.54 secs, 6,441,144,248 bytes)
--    λ> libreDeCuadrados2 9699690
--    True
--    (4.78 secs, 1,940,781,632 bytes)
--    λ> libreDeCuadrados3 9699690
--    True
--    (0.01 secs, 561,400 bytes)
--    λ> libreDeCuadrados4 9699690
--    True
--    (0.01 secs, 568,160 bytes)
--    λ> libreDeCuadrados5 9699690
--    True
--    (0.01 secs, 567,536 bytes)
--
--    λ> libreDeCuadrados3 (product (take 30000 primes))
--    True
--    (2.30 secs, 2,369,316,208 bytes)
--    λ> libreDeCuadrados4 (product (take 30000 primes))
--    True
--    (6.68 secs, 4,565,617,408 bytes)
--    λ> libreDeCuadrados5 (product (take 30000 primes))
--    True
--    (5.54 secs, 3,411,701,752 bytes)

from timeit import Timer, default_timer
from sys import setrecursionlimit
from sympy import primefactors, primerange
from hypothesis import given, strategies as st

setrecursionlimit(10**6)

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

def libreDeCuadrados1(n: int) -> bool:
    return [x for x in range(2, n + 2) if n % (x**2) == 0] == []

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

# divisores(n) es la lista de los divisores del número n. Por ejemplo,
#    divisores(30)  ==  [1,2,3,5,6,10,15,30]
def divisores1(n: int) -> list[int]:
    return [x for x in range(1, n + 1) if n % x == 0]

# primo(n) se verifica si n es primo. Por ejemplo,
#    primo(30)  == False
#    primo(31)  == True
def primo1(n: int) -> bool:
    return divisores1(n) == [1, n]

# divisoresPrimos(x) es la lista de los divisores primos de x. Por
# ejemplo,
#    divisoresPrimos(40) == [2, 5]
#    divisoresPrimos(70) == [2, 5, 7]
def divisoresPrimos1(x: int) -> list[int]:
    return [n for n in divisores1(x) if primo1(n)]

# producto(xs) es el producto de los elementos de xs. Por ejemplo,
#    producto([3, 2, 5])  ==  30
def producto(xs):
    if xs:
        return xs[0] * producto(xs[1:])
    return 1

def libreDeCuadrados2(x):
    return x == producto(divisoresPrimos1(x))

# 3ª solución
# ===========

def libreDeCuadrados3(n: int) -> bool:
    if n % 2 == 0:
        return n % 4 != 0 and libreDeCuadrados3(n // 2)

    def aux(m, xs):
        if m == 1:
            return True
        if xs == []:
            return True
        if m % xs[0] == 0:
            return m % (xs[0]**2) != 0 and aux(m // xs[0], xs[1:])
        return aux(m, xs[1:])
    return aux(n, range(3, n + 1, 2))

# 4ª solución
# ===========

def libreDeCuadrados4(x):
    return x == producto(primefactors(x))

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

# La propiedad es
@given(st.integers(min_value=2, max_value=1000))
def test_libreDeCuadrados(n):
    assert libreDeCuadrados1(n) ==\
           libreDeCuadrados2(n) ==\
           libreDeCuadrados3(n) ==\
           libreDeCuadrados4(n)

# La comprobación es
#    src> poetry run pytest -q numeros_libres_de_cuadrados.py
#    1 passed in 0.59s

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

def tiempo(e):
    """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('libreDeCuadrados1(9699690)')
#    2.66 segundos
#    >>> tiempo('libreDeCuadrados2(9699690)')
#    2.58 segundos
#    >>> tiempo('libreDeCuadrados3(9699690)')
#    0.00 segundos
#    >>> tiempo('libreDeCuadrados4(9699690)')
#    0.00 segundos
#
#    >>> n = producto(list(primerange(1, 25000)))
#    >>> tiempo('libreDeCuadrados3(n)')
#    0.42 segundos
#    >>> tiempo('libreDeCuadrados4(n)')
#    0.14 segundos