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

Crivo de Eratóstenes Simples em Java

Algoritmo para Gerar um Sudoku NxN válido

Usando Enhanced For

Conversor de bases

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