Algoritmos para Teoria dos Números

Publicado por Humberto Henrique Campos Pinheiro 14/05/2005 (última atualização em 02/07/2012)

[ Hits: 10.943 ]

Download algcalc2.java

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ões atualizadas deste script

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

Download Algebra.java


Esconder código-fonte

/*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;
      }
   }
   
}

Scripts recomendados

Ordenação de vetores com letras do alfabeto (atualizado)

Planilha de cálculo para multa judicial

Código Java para validar CPF

Pequeno algoritmo para determinar se um número é primo ou não entre 1 e 10000

Exemplo de sobrecarga de métodos


  

Comentários
[1] Comentário enviado por removido em 24/06/2012 - 23:20h

Na presente data deu algum tipo de erro, não sei se pelas mudanças no Java de agora.

[2] Comentário enviado por humbhenri em 02/07/2012 - 12:56h

Submeti uma nova versão.

[3] Comentário enviado por removido em 03/07/2012 - 14:06h

Baixei e testei.
Desta vez funcionou.
Gostei.
Parabéns.

[4] Comentário enviado por humbhenri em 03/07/2012 - 14:13h

Bom aproveitando o ensejo já indico algumas melhorias que podem ser feitas mas vai demandar um tempinho. Primeiro quando eu fiz ainda não sabia muito Java hoje sei mais um pouco; tem duas coisas que me incomodam nesse código, principalmente. Convenções de código da Sun/Oracle (tipo nomes de classe em maiúscula) e usar thread para fazer os cálculos, veja que os cálculos rodam na mesma thread da interface gráfica causando congelamento, o que é muito ruim. Quando tiver um tempinho vou ver se coloco uma nova versão. Abraços.

[5] Comentário enviado por removido em 04/07/2012 - 05:03h

Bem observada essa implementação da thread.
Ainda há como aumentar os limites dos números, não é?

[6] Comentário enviado por humbhenri em 04/07/2012 - 10:44h

Dá sim, no crivo por exemplo dá pra aumentar o máximo ali pra um milhão fácil, testei aqui com um core 2 duo rodou em 1 segundo.


Contribuir com comentário




Patrocínio

Site hospedado pelo provedor RedeHost.
Linux banner
Linux banner

Destaques

Artigos

Dicas

Tópicos

Top 10 do mês

Scripts