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.

• Download algcalc2.java
• Enviar nova versão

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

Algoritmo para Gerar um Sudoku NxN válido

Pilha em Java

Exemplo de sobrecarga de métodos

Código Java para validar CPF

Script para cálculo de distâncias na superfície terrestre utilizando coordenadas geográficas