#esPrimo: int -> bool
#True si n>1 es primo
#ej: esPrimo(2)->True  (par primo)
#ej: esPrimo(6)->False (par no primo)
#ej: esPrimo(13)->True (impar primo)
#ej: esPrimo(9)->False (impar no primo)
def esPrimo(n):
  assert type(n)==int and n>1
  if n%2==0:
      #numero par
      return n==2
  else:
      #numero impar
      def _esPrimo(n,divisor):
          if divisor*divisor > n: 
              return True
          elif n % divisor == 0: 
              return False
          else:
              return _esPrimo(n,divisor+2)
      return _esPrimo(n,3)
assert esPrimo(2)
assert not esPrimo(6)
assert esPrimo(13)
assert not esPrimo(9)

#usando instrucciones if sin else y parámetro con valor por omisión
def esPrimo(n):
  assert type(n)==int and n>1
  if n%2==0: return n==2
  def _esPrimo(n,divisor=3):
    if divisor*divisor > n: return True
    if n % divisor == 0: return False
    return _esPrimo(n,divisor+2)
  return _esPrimo(n)

#usando condiciones compuestas
def esPrimo(n):
  assert type(n)==int and n>1
  def _esPrimo(n,divisor=3):
      return divisor*divisor>n or n%divisor!=0 and  _esPrimo(n,divisor+2)
  return n%2!=0 and _esPrimo(n) or n==2
assert esPrimo(2)
assert not esPrimo(6)
assert esPrimo(13)
assert not esPrimo(9)

#primosEnRango: int int ->
#escribir primos entre x e y
#ej primosEnRango(2,10) escribe 2 3 5 7
def primosEnRango(x,y):
    assert type(x)==int and x>=2 
    assert type(y)==int
    if x>y: return
    if esPrimo(x): print(x)
    primosEnRango(x+1,y)
#primosEnRango(2,10)

#siguientePrimo: int -> int
#primo siguiente a n
#ej: siguientePrimo(7)->11, siguientePrimo(2)->3
def siguientePrimo(n):
    assert type(n)==int and n>1
    if n%2==0:
        sgte=n+1
    else:
        sgte=n+2
    if esPrimo(sgte): 
        return sgte
    else:
        return siguientePrimo(sgte)
assert siguientePrimo(7)==11
assert siguientePrimo(2)==3

#siguientePrimo: int -> int
#primo siguiente a n
#ej: siguientePrimo(7)->11
def siguientePrimo(n):
    assert type(n)==int and n>1
    def _siguientePrimo(n): 
        if esPrimo(n): 
            return n
        else:
            return _siguientePrimo(n+2)
    if n%2==0:
        return _siguientePrimo(n+1)
    else:
        return _siguientePrimo(n+2)
assert siguientePrimo(7)==11
assert siguientePrimo(2)==3

#factoresPrimos: int ->
#escribe factores primos de n>=1
#ej: factoresPrimos(24) escribe 2**3 y 3**1
def factoresPrimos(n,factor=2):
    assert type(n)==int and n>=1
    #caso base
    if n==1: return
    #calcular y escribir potencia p de factor primo
    def potencia(n,factor):
        if n % factor != 0: return 0
        return 1+potencia(n//factor, factor)
    p=potencia(n,factor)
    if p>0: print('factor:',factor,'potencia:',p)
    #recursion
    factoresPrimos(n//factor**p,siguientePrimo(factor))

#factoresPrimosRango: int int ->
#escribe factores primos de números entre x e y
#ej: factoresPrimosRango(25,30) escribe factores de 25,...,30
def factoresPrimosRango(x,y):
    assert type(x)==int and x>=2 and type(y)==int
    #caso base
    if x>y: return
    #escribir factores primos de x
    print('factores primos de',x)
    factoresPrimos(x)
    print()
    #recursion
    factoresPrimosRango(x+1,y)

from mcd import *
#sonCoprimos: int int -> bool
#True si x e y no tienen divisores comunes
#ej: sonCoprimos(4,9)->True
#ej: sonCoprimos(18,24)->False
def sonCoprimos(x,y):
  assert type(x)==int and x>1
  assert type(y)==int and y>1
  assert x != y
  return mcd(x,y)==1 #maximo común divisor
assert sonCoprimos(4,9)
assert not sonCoprimos(18,24)

#coprimosEnRango: int int -> 
#escribe coprimos entre números x e y
#ej: coprimosEnRango(2,5) escribe 2 3,2 5,3 4,3 5,4 5
def coprimosEnRango(x,y):
    assert type(x)==int and x>1
    assert type(y)==int and y>1
    #caso base
    if x>=y: return
    #coprimos de x entre x+1 e y
    def coprimosDe(n,x,y):
        if x>y: return
        if sonCoprimos(n,x): print(n,x)
        coprimosDe(n,x+1,y)
    coprimosDe(x,x+1,y)
    #recursion
    coprimosEnRango(x+1,y)