Algoritmo de Fatoração de Fermat (FFA) em C
Publicado por Perfil removido (última atualização em 10/04/2012)
[ Hits: 10.846 ]
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; }
Pilhas Encadeadas Detalhadamente
Contar elementos de uma lista encadeada
Aprenda a Gerenciar Permissões de Arquivos no Linux
Como transformar um áudio em vídeo com efeito de forma de onda (wave form)
Como aprovar Pull Requests em seu repositório Github via linha de comando
Visualizar arquivos em formato markdown (ex.: README.md) pelo terminal
Dando - teoricamente - um gás no Gnome-Shell do Arch Linux
Como instalar o Google Cloud CLI no Ubuntu/Debian
Mantenha seu Sistema Leve e Rápido com a Limpeza do APT!
Procurando vídeos de YouTube pelo terminal e assistindo via mpv (2025)
Sinto uma leve lentidão ao arrastar, miniminizar e restauras as janela... (0)
Zorin OS - Virtual Box não consigo abrir maquinas virtuais (6)
Iinstalar o Scanner Kodak i940 no Linux Mint 19/20? (3)