Algoritmo de Fatoração de Fermat (FFA) em C
Publicado por Perfil removido (última atualização em 10/04/2012)
[ Hits: 10.559 ]
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; }
Script MakePach para correção de platarforma 32 bits para 64
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
E a guerra contra bots continua
Tradução do artigo do filósofo Gottfried Wilhelm Leibniz sobre o sistema binário
Conheça o firewall OpenGFW, uma implementação do (Great Firewall of China).
Instalando o FreeOffice no LMDE 6
Anki: Remover Tags de Estilo HTML de Todas as Cartas
Colocando uma opção de redimensionamento de imagem no menu de contexto do KDE
Failed to start Zabbix Server (2)
Gentoo bane contribuições de código feitas com IA (8)
Ubuntu — tentando iniciar o windows? (3)
[Shell Script] Script para desinstalar pacotes desnecessários no OpenSuse
[Shell Script] Script para criar certificados de forma automatizada no OpenVpn
[Shell Script] Conversor de vídeo com opção de legenda
[C/C++] BRT - Bulk Renaming Tool
[Shell Script] Criação de Usuarios , Grupo e instalação do servidor de arquivos samba