Algoritmo de Fatoração de Fermat (FFA) em C
Publicado por Perfil removido (última atualização em 10/04/2012)
[ Hits: 10.569 ]
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; }
Conversão de Decimal para Binário
S. MarioBros - Editor de fase 0.1
Agenda feita em C usando árvore binária
Mudando Cor da Letra e Fundo de Tela
Atenção a quem posta conteúdo de dicas, scripts e tal (2)
Manutenção de sistemas Linux Debian e derivados com apt-get, apt, aptitude e dpkg
Melhorando o tempo de boot do Fedora e outras distribuições
Como instalar as extensões Dash To Dock e Hide Top Bar no Gnome 45/46
Como Atualizar Fedora 39 para 40
Instalar Google Chrome no Debian e derivados
Consertando o erro do Sushi e Wayland no Opensuse Leap 15
Instalar a última versão do PostgreSQL no Lunix mantendo atualizado
Flathub na sua distribuição Linux e comandos básicos de gerenciamento
ASRock H310CM-HG4 vs Linux [RESOLVIDO] (18)
Microfone do meu headset não é recinhecido. Meu notebook é um Acer Asp... (12)