Algoritmo de Fatoração de Fermat (FFA) em C
Publicado por Perfil removido (última atualização em 10/04/2012)
[ Hits: 10.753 ]
FFA: Fermat Factoring Algorithm (Algoritmo de Fatoração de Fermat)
Procedimento simples 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, entao 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.
Obs[1]: Possível otimizá-lo. Este fica a exemplo de contexto.
Obs[2]: Compilar com a seguinte linha de comando:
(bem lembrado pela moderação) :-)
gcc fermat001.c -o fermat001 -lm
-lm faz ligação com a libm, biblioteca de funções matemáticas do C.
#include <stdio.h> #include <math.h> /* Compilar com a seguinte linha de comando: gcc fermat001.c -o fermat001 -lm Procedimento simples de fatoracao inventado por Pierre de Fermat: Todo numero pode ser escrito como diferenca de dois numeros elevados ao quadrado: n = a*a - b*b; Esta expressão pode ser escrita como n = (a+b) (a-b), onde a soma e a subtracao sao dois fatores do numero em questao. Se n eh primo, a-b = 1, a+b=n; Para numeros com diversos fatores e divisores existem diversos a e b que satisfazem a expressao. Este algoritmo testa em progressao diversos valores "b" em i + j*j, com i=n no primeiro passo. Se i + j*j for um quadrado perfeito, entao calcula-se com base nisto os correspondentes a e b da expressoo anterior, tendo-se entao encontrado um fator. Fator que nao é necessariamente um numero primo. */ typedef unsigned long int ulint; #define VALOR 48292699 ulint fator (ulint n) { if (!n) return 0; // caso n = 0 if (!(n>>1)) return 1; // caso n = 1 if (~n&1) return ((n>>1)>2?2:(n>>1)); // caso n par ulint i=n, j=0, k=0; do { i += j; k = (int) sqrt((double)i); j += ((!j)?1:2); // ainda ha como reduzir pela metade // o numero de repeticoes deste laco } while (i-k*k>0); k += (j-1)>>1; n /= k; return (n>k?k:n); } int main (void) { ulint n = VALOR; ulint p=1, q=1; do { p = fator (n); do { // este loop usa o fator encontrado anteriormente e se // assegura de que ele seja o menor q = fator (p); p /= q; } while (q>1); // isto faz perder tempo, mas não retorna fatores compostos n /= p; if (p!=1) printf ("%u ", p); else printf ("%u\n", n); } while (p>1); return 0; }
Gerenciamento de Área de Alocação Dinâmica (Listas Encadeadas)
Passkeys: A Evolução da Autenticação Digital
Instalação de distro Linux em computadores, netbooks, etc, em rede com o Clonezilla
Título: Descobrindo o IP externo da VPN no Linux
Armazenando a senha de sua carteira Bitcoin de forma segura no Linux
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Instalando Brave Browser no Linux Mint 22
vídeo pra quem quer saber como funciona Proteção de Memória:
Encontre seus arquivos facilmente com o Drill
Mouse Logitech MX Ergo Advanced Wireless Trackball no Linux
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Como abrir o pycharm no linux (2)
VMs e Interfaces de Rede desapareceram (12)