primality.ex

defmodule Primality do
  # O jeito "ingênuo" de checar por primalidade é você simplesmente verificar
  # se o número tem divisores. Ou seja, você pega todos os números menores
  # que o seu número-alvo (começando em 2, pois 1 divide todos os números)
  # e verifica se eles dividem o número (ou seja, se o resto da divisão -
  # função `rem/1` - é igual a 0).
  #
  # Também precisamos de um caso especial para 1, que não tem divisores mas não
  # é primo.
  def check_naive(1), do: false
  
  def check_naive(n) do
    # A função `Enum.any?` recebe um iterável - aqui, um range - e
    # uma função, e retorna se a função retorna `true` para algum
    # elemento do range.
    not Enum.any?(2..n-1, fn i -> rem(n, i) == 0 end)
  end

  # Todavia, o teste acima é ineficiente - pois se o número tiver algum divisor,
  # esse divisor será menor ou igual à raiz quadrada do número.
  # (Lembre que a raiz quadrada é o número tal que a * a = número alvo.
  # Se existir um divisor maior que a raiz quadrada, o número pelo qual
  # ele é multiplicado para chegar ao alvo precisa ser menor que a raiz quadrada -
  # portanto, só precisamos testar até a raiz)
  def check_up_to_sqrt(1), do: false

  def check_up_to_sqrt(n) do
    # A função :math.sqrt retorna o valor da raiz como float.
    # Portanto, usamos a função piso (`floor`) que retorna o maior
    # inteiro menor que um dado float para converter.
    # Essa conversão cria uma ineficiência e poderia ser eliminada com uma
    # geração mais inteligente do iterável, como veremos abaixo.
    not Enum.any?(2..floor(:math.sqrt(n)), fn i -> rem(n, i) == 0 end)
  end

  # O algoritmo acima já funciona suficientemente bem pra maioria dos casos,
  # mas dá pra gente melhorar ele com um pouquinho mais de matemática.
  # Uma regra simples que podemos aplicar é que todo primo maior ou igual a 5
  # é um número do formato 6n+-1, para algum n inteiro.
  #
  # Isso pode ser verificado a seguir -
  # Para qualquer n, temos os seguintes números:
  #
  # 6n -> é múltiplo de 6 e portanto divisível por 2 e 3;
  # 6n + 1 -> pode ser primo
  # 6n + 2 -> é par e portanto múltiplo de 2
  # 6n + 3 -> é um múltiplo de 6 + 3 e portanto múltiplo de 3
  # 6n + 4 -> é par e portanto múltiplo de 2
  # 6n + 5 -> pode ser primo e também pode ser representado como 6(n+1)-1
  #
  # Portanto, os únicos números que podem ser primos são 2, 3, e números da forma
  # 6n +- 1.
  #
  # Iremos checar apenas números desse formato usando um Stream (uma lista potencialmente infinita,
  # gerada sob demanda)
  def check_stream(1), do: false

  def check_stream(2), do: true

  def check_stream(3), do: true
  
  def check_stream(n) do
    # A função Stream.unfold recebe um "acumulador" inicial - aqui um número
    # e uma função que deve receber o acumulador atual e retornar um elemento
    # e um novo acumulador.
    #
    # Abaixo, a gente usa um átomo pra marcar se estamos no elemento 6n-1 ou
    # no elemento 6n + 1.
    #
    # A geração do Stream continua até que a função geradora retorne `nil`.
    candidates_stream = Stream.unfold(2, fn
      2 -> {2, 3}
      3 -> {3, {:first, 5}} # 5 é o primeiro valor 6n - 1
      {_, i} when i * i > n -> nil # Se o valor é maior que a raiz quadrada, paramos
      {:first, i} -> {i, {:second, i + 2}} # Se estamos no valor 6n-1, somamos 2 para chegar a 6n+1
      {:second, i} -> {i, {:first, i + 4}} # Se estamos no valor 6n+1, somamos 4 para chegar a 6n+5 = 6(n+1)-1
    end)

    not Enum.any?(candidates_stream, fn i -> rem(n, i) == 0 end)
  end

  # Uma coisa importante de notar é que nenhum desses métodos é apropriado
  # pros primos gigantescos que encontramos em aplicações criptográficas.
  #
  # Nesses casos, os algoritmos necessários são mais complexos - num próximo post
  # devo falar um pouco sobre eles.
end