Algoritmo de Fatoração de Fermat (FFA) em Ruby
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.
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.
Descrição
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.
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.
#!/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
http://www.vivaolinux.com.br/script/Algoritmo-de-Fatoracao-de-Fermat-(FFA)-em-C
http://www.vivaolinux.com.br/script/Algoritmo-de-Fatoracao-de-Fermat-(FFA)-em-Perl