Algoritmos para Teoria dos Números
Publicado por Humberto Henrique Campos Pinheiro 14/05/2005 (última atualização em 02/07/2012)
[ Hits: 11.440 ]
Download Algebra.java (versão 2)
Alguns algoritmos para estudar a álgebra da teoria dos números, base do sistema de criptografia RSA (e de outros). Contém crivo de Erastótenes, algoritmo euclidiano estendido, Mersenne e o método de Fermat para ver se um número é primo. Qualquer dúvida ou comentários estamos ouvindo.
Versão 2 - Enviado por Humberto Henrique Campos Pinheiro em 25/06/2012
Changelog: Remove código que causa warnings, muda nome da classe pública
/*Interface Grafica para algoritmos de Álgebra Humberto Henrique */ import javax.swing.*; import java.awt.event.*; import java.awt.*; public class algcalc2 extends JFrame{ private JLabel label; private JButton euclid, ferm, erastotenes, mers; private final int x=300;//dimensões private final int y=200;// //configura a interface public algcalc2(){ super("Algoritmos para Álgebra A"); //painel Container container=getContentPane(); container.setLayout(new FlowLayout()); //botões euclid=new JButton("Algoritmo Euclidiano Estendido"); euclid.setToolTipText("Calcula o mdc de dois números inteiros"); container.add(euclid); ferm=new JButton("Algoritmo de Fermat"); ferm.setToolTipText("Informa se um número é primo"); container.add(ferm); erastotenes=new JButton("Crivo de Erastótenes"); erastotenes.setToolTipText("Mostra todos os primos menores ou iguais ao número dado"); container.add(erastotenes); mers=new JButton("Número de Mersenne"); mers.setToolTipText("Calcula o número M(n) dado n"); container.add(mers); Trata_Euclid tb=new Trata_Euclid(); euclid.addActionListener(tb); Trata_fermat tf=new Trata_fermat(); ferm.addActionListener(tf); Trata_crivo tc=new Trata_crivo(); erastotenes.addActionListener(tc); Trata_mers tm=new Trata_mers(); mers.addActionListener(tm); //centralizado em 800x600 setCursor(new Cursor(CROSSHAIR_CURSOR)); setLocation(400-x/2,300-y/2); setSize(x, y); setResizable(false); setVisible(true); } //executa public static void main(String[] args){ algcalc2 a=new algcalc2(); a.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE); } //tratamento de eventos do botao private class Trata_Euclid implements ActionListener{ public void actionPerformed(ActionEvent event){ try{ int a=Integer.parseInt(JOptionPane.showInputDialog("Digite o primeiro número")); int b=Integer.parseInt(JOptionPane.showInputDialog("Digite o segundo número")); euclides e=new euclides(a,b); JOptionPane.showMessageDialog(null, e); } catch(NumberFormatException exc){ JOptionPane.showMessageDialog(null,"Formato de Número Incorreto","Erro", JOptionPane.ERROR_MESSAGE); actionPerformed(event); } } } private class Trata_fermat implements ActionListener{ public void actionPerformed(ActionEvent event){ try{ int a=Integer.parseInt(JOptionPane.showInputDialog("Digite o número")); if (a==1){ JOptionPane.showMessageDialog(null,"O número 1 não é primo nem composto", ":|",JOptionPane.ERROR_MESSAGE);} else{ fermat f=new fermat(a); JOptionPane.showMessageDialog(null, f); } } catch(NumberFormatException exc){ JOptionPane.showMessageDialog(null,"Formato de Número Incorreto","Erro", JOptionPane.ERROR_MESSAGE); actionPerformed(event); } } }//fim de Trata_fermat private class Trata_crivo implements ActionListener{ public void actionPerformed(ActionEvent event){ try{ int a=Integer.parseInt(JOptionPane.showInputDialog("Digite o número")); crivo c=new crivo(a); JTextArea area=new JTextArea(c.toString(), 10, 20); area.append("\nEncontrados "+c.quantidade()+" primos"); area.setEditable(false); JScrollPane scroll=new JScrollPane(area); JOptionPane.showMessageDialog(null,scroll,"Primos menores ou iguais a "+a, JOptionPane.INFORMATION_MESSAGE); } catch(NumberFormatException exc){ JOptionPane.showMessageDialog(null,"Formato de Número Incorreto","Erro", JOptionPane.ERROR_MESSAGE); actionPerformed(event); } } }//fim de Trata_crivo private class Trata_mers implements ActionListener{ public void actionPerformed(ActionEvent event){ try{ int n=Integer.parseInt(JOptionPane.showInputDialog("Digite o número")); if(n<64){ long l=(long) Math.pow(2,n)-1; JOptionPane.showMessageDialog(null,"O número é: "+l,"Número de Mersenne para "+n, JOptionPane.INFORMATION_MESSAGE); } else JOptionPane.showMessageDialog(null,"O número não pode ser maior que 63 bits","Erro", JOptionPane.ERROR_MESSAGE); } catch(NumberFormatException exc){ JOptionPane.showMessageDialog(null,"Formato de Número Incorreto","Erro", JOptionPane.ERROR_MESSAGE); actionPerformed(event); } } } } /***************** Algoritmos para Álgebra********************************/ //Algoritmo de Fermat: Determina um fator de um inteiro class fermat{ private int n, x; private boolean primo; public fermat(int a){ this.n=a; algoritmo(n); } public void configNum(int n){ this.n=n; algoritmo(n); } private void algoritmo(int num){ double aux; int y; if(num%2==0){primo=false; x=2;} else{ x=(int) Math.sqrt(n); while(true){ x++; aux=Math.sqrt(x*x-n); y=(int) aux; if(x==(n+1)/2){primo=true; break;} if(aux==y){primo=false; x=x+y; break;} } } } public String toString(){ if(primo) return "O número é primo"; else return "Fator de "+n+" : "+x; } } /*Crivo de Erastótenes Programador: Humberto Henrique*/ class crivo{ private int contador=0, n; private String lista;//lista dos primos ímpares<=n private byte[] v; public crivo(int m){ if(m<50000){ if (m%2==1) m++; n=m; v=new byte[n/2]; for(int i=0; i<v.length; i++) v[i]=1; algoritmo(n); } else lista="O algoritmo é ineficiente para um número tão grande"; } private void algoritmo(int n){ lista="2\n"; int P=3, T; do{ if(v[((P-1)/2)]==0) P=P+2; else{ T=P*P; while(T<=n){ v[((T-1)/2)]=0; T=T+2*P; } P=P+2; } }while(P*P<=n); int aux; v[0]=0; /* Se p*p>n os números primos são aqueles da forma 2j+1 para os quais a j-ésima entrada do vetor é 1 */ for(int j=0; j<v.length; j++){ if (v[j]==1 ){ aux=2*j+1; lista+=aux+"\n"; contador++; } } contador++;//para contar o 2 }//fim do algoritmo public String toString(){return lista;} public int quantidade(){return contador;} } //Algoritmo Euclidiano Estendido class euclides{ private int a,b,alfa,beta,mdc; public euclides(int n, int m){ a=n; b=m; calc(a,b); } public String toString(){ return new String("mdc("+a+","+b+")="+alfa+"*"+a+"+"+beta+"*"+b+"="+mdc); } private void calc(int a, int b){ //obviedades if (a==b){alfa=0; beta=1; mdc=a;} else{ int x0, x1, x2, y0, y1, y2, r, q,maior,menor; if(a>b){maior=a; menor=b;} else {maior=b; menor=a;} x0=1; x1=0; y0=0; y1=1; r=q=alfa=beta=x2=y2=1; while(r!=0){ r=maior%menor; q=maior/menor; x2=x0-q*x1; y2=y0-q*y1; x0=x1; x1=x2; y0=y1; y1=y2; maior=menor; menor=r; } if(a>b){ alfa=x0; beta=y0; } else{ alfa=y0; beta=x0; } mdc=alfa*a + beta*b; } } }
Código para validar CPF e CNPJ otimizado
Pesquisa Binaria em um vetor ordenado
Código para validar CPF e CNPJ otimizado
Enviar mensagem ao usuário trabalhando com as opções do php.ini
Meu Fork do Plugin de Integração do CVS para o KDevelop
Compartilhando a tela do Computador no Celular via Deskreen
Como Configurar um Túnel SSH Reverso para Acessar Sua Máquina Local a Partir de uma Máquina Remota
Configuração para desligamento automatizado de Computadores em um Ambiente Comercial
Compartilhamento de Rede com samba em modo Público/Anônimo de forma simples, rápido e fácil
Cups: Mapear/listar todas as impressoras de outro Servidor CUPS de forma rápida e fácil
Criando uma VPC na AWS via CLI
Arch Linux - Guia para Iniciantes (2)
Problemas ao instalar o PHP (11)
Tem como instalar o gerenciador AMD Adrenalin no Ubuntu 24.04? (15)
Tenho dois Link's ( IP VÁLIDOS ), estou tentando fazer o failover... (0)