FFA: Fermat Factoring Algorithm (Algoritmo de Fatoração de Fermat)

Método de fatoração inventado por Pierre de Fermat:

Todo numero pode ser escrito como diferença de dois números elevados ao quadrado:

n = a² - b², ou n = a*a - b*b;

Esta expressão pode ser escrita como n = (a+b) * (a-b), ou n = (a+b) (a-b), onde a soma e a subtração dos valores "a" e "b" são dois fatores do número em questão.

Se n é primo, então a-b = 1 e a+b=n;

Para números com diversos fatores e divisores existem diversos "a" e "b" que satisfazem a expressão.

Este algoritmo testa em progressão diversos valores "b" em "i + j*j", ou i + j², com i=n no primeiro passo.

Se i + j*j for um quadrado perfeito, então calcula-se com base nisto os correspondentes a e b da expressão anterior, tendo-se então encontrado um fator.

Fator este que não é necessariamente um número primo.

Este programa trabalha com os fatores sendo escritos em uma lista, sendo pegos um a um até o final.

A função de fatoração retorna uma estrutura com um par de números que se multiplicados retornam o valor de entrada, ordenados em maior e menor.

No retorno, a parcela menor substitui a posição do elemento pego anteriormente e a parcela maior é inserida ao fim da lista principal.

Quando o valor menor do par é um, o valor maior é um número primo, então continua-se com o próximo elemento da lista principal, encerrando-se ao último elemento.

Por último, a lista de fatores é ordenada para apresentação.

Obs[1]: Por enquanto não fatora números negativos.
Obs[2]: É possível ainda um teste que reduz o número de repetições do while da sub-rotina.

• Download fermat001.rb
• Enviar nova versão

Esconder código-fonte

#!/usr/bin/ruby

VALOR = 3*5*7*3*11*31*43*31
#VALOR = 2*2*2*2*2*2*2*2
#VALOR = 984*365*5*36*3*275*257*4257*4258*24890

def fator n

   return [-1, 1] if n<0
   return [0, 1] if n==0
   return [1, 1] if n==1
   return [2, 1] if n==2
   return [n>>1,2] if ((n%2)==0)

   i, j, k = n, 0, 0

   i += j and k = (i**(0.5)).to_i and j += ((j==0)?1:2) while (i-k*k>0)

   k += (j-1)>>1;
   n /= k;

   return [n,k] if n>=k
   return [k,n] if n<k

end

fatores1 = [VALOR]
p, q = 1, 0

while q<fatores1.length do
   while p>=1 do
      fatores1[q], p = fator(fatores1[q])
      p==1 ? break : fatores1 += [p]
   end
   q += 1
end

(fatores1.sort).each do |i|
   print i, " "
end

puts

Uso de if em Ruby (2)

Uso simples de if e else em Ruby

Agenda telefônica em Ruby que grava os dados em um txt

Controle de maior e menor de idade em Ruby

Importar endereços do Claws no Evolution (entre outros)