VB .NET -  Números Primos (Eratosthenes)


Este artigo é para quem gosta de matemática mas , como não poderia deixar de ser, envolve a linguagem VB .NET.

Vou mostrar uma implementação do algoritmo de Eratosthenes usando a linguagem VB .NET para encontrar números primos.

Antes um pouco de teoria e  história...

Um inteiro maior do que um é chamado de número primo se seus únicos divisores positivos (fatores) forem o número um e ele mesmo.

Por exemplo, os divisores primos de 10 são 2 e 5; e os primeiros seis números primos são 2, 3, 5, 7, 11 e 13.  (O número 1 não é primo)

O Crivo de Eratosthenes é a forma mais eficiente de encontrar números primos pequenos  (menores do que 1.000.000).

Para números primos maiores existem outros métodos.

Em matemática , o crivo de Eratosthenes pode ser usado para encontrar os números primos até um valor especificado.

O algoritmo foi criado por Eratosthenes um antigo matemático grego.

 


 

Como exemplo e usando o algoritmo de Eratosthenes vamos encontrar todos os números primos menores ou iguais a 30, para isso devemos executar os seguintes passos:

- Primeiro gerar uma lista de inteiros a partir do número 2 até o número 30;

  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30

- Remover os múltiplos de 2 a partir da lista original começando a partir do número 4 :
  2  3     5     7     9    11    13    15    17    19    21    23    25    27    29

- O primeiro número na lista depois de 2 é 3 , logo devemos remover os múltiplos de 3 a partir da lista original começando a partir do número 9:
  2  3     5     7          11    13          17    19          23    25          29

- O primeiro número na lista depois de 3 é o 5; logo vamos remover os múltiplos de 5 a partir da lista original iniciando no 25;
  2  3     5     7          11    13          17    19          23                29

- O primeiro número na lista depois do 5 é o 7, mas 7 ao quadrado é igual a 49 que é maior que 30 então o processo é encerrado.
A lista final de todos os número primos menores ou igual a 30 é:

  2  3     5     7          11    13          17    19          23                29

Entendeu como funciona ???

Vou usar o Visual Basic 2008 Express Edition e criar um projeto do tipo Windows Forms Application com o nome numerosPrimos;

A seguir vou incluir um novo formulário através do menu  Project -> Add Windows Form com o nome frmMain.vb e definir sua propriedade IsMdiContainer como sendo True;

Depois a partir do ToolBox vou incluir um novo controle MenuStrip e definir um menu com duas opções conforme a figura abaixo:

Vejamos agora duas implementações do algoritmo feito na linguagem VB .NET.

1- ) Usando o crivo de Eratosthenes

Na primeira opção do menu vamos chamar o formulário form1.vb conforme o código abaixo:

Private Sub AlgoritimoDeToolStripMenuItem_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles AlgoritimoDeToolStripMenuItem.Click

My.Forms.Form2.Show()
Form2.MdiParent =
Me

End Sub

A seguir vamos incluir no formulário form1.vb um controle TextBox, um Button e um ListBox conforme o leiaute da figura abaixo:

No evento Click do botão Calcular vamos incluir o código abaixo:

  Private Sub btnCalcula_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles btnCalcula.Click
        If txtPrimos.Text <> String.Empty Then
            Dim valor As Integer = CType(txtPrimos.Text, Integer)
            If valor < 2 Then
                MsgBox("Informe um número maior que um.")
                Exit Sub
            End If
            Dim primos(valor - 1) As Int32
            primos = Calculo.geraListaNumeroPrimos1(valor)
            lstPrimos.Items.Clear()
            For Each i In primos
                If i > 0 Then
                    lstPrimos.Items.Add(i)
                End If
                Application.DoEvents()
            Next
        Else
            MsgBox("Informe um valor para cálculo.")
        End If
    End Sub

 

Todo o cálculo esta sendo feito pelo método geraListaNumeroPrimos1(valor) que implementa o algoritmo de Eratosthenes.

Para isso vamos incluir uma classe no projeto; Selecione o menu Project -> Add Class e informe o nome Calculo.vb e clique em Add;

Vamos definir na classe as variáveis globais NumeroMaximo para determinar até que número poderemos fazer os cálculos e um array para armazenar os números primos obtidos chamado PrimosArmazenados()  conforme abaixo:

Private Const NumeroMaximo As Integer = 8000000
Private Shared PrimosArmazenados As New BitArray(NumeroMaximo, True)

A seguir vamos definir o método geraListaNumeroPrimos1(valor) com o seguinte código:

Public Shared Function geraListaNumeroPrimos1(ByVal NumeroMaximo As Int32) As Int32()
        Dim primos(NumeroMaximo) As Int32
        Dim index As Integer = 1
        Dim contador As Integer
        Dim i As Integer = 0
        Do While (index <= (NumeroMaximo - 1))
            index += 1
            'separa os números primos atribuindo false aos não primos
            If (PrimosArmazenados(index) = True) Then
                For contador = index * 2 To NumeroMaximo - 1 Step index
                    PrimosArmazenados(contador) = False
                Next contador
            End If
        Loop
        For contador = 2 To NumeroMaximo 
            If (GetBit(contador) = 1) Then
                primos(contador) = contador
            End If
        Next contador
        Return primos
    End Function   

Nota: Segue abaixo uma versão em C# que encontrei na web mas que não testei:

using System;
class App 
{
    public static int Main(String[] args) 
    {        
        int num;
        bool[] flags = new bool[51];
        long i, k;
        int count = 0;      
        num = System.Convert.ToInt32(args[0]);
        if(num < 1) num = 1;        
        while(num-- > 0) 
        {
            count = 0;
            for(i = 2; i <= 50; i++) 
            {
                flags[i] = true;
            }
            for(i = 2; i <= 50; i++) 
            {
                if(flags[i]) 
                {
                    for(k = i + i; k <= 50; k += i) 
                    {
                        flags[k] = false;
                    }
                    count++;
                }
            }
        }
        Console.WriteLine("Count: " + count.ToString());
        return(0);
    }
}

Vamos precisar definir também o método GetBit() a seguir que é usado para atribuir o valor de True ou False a um número indicando se ele é primo ou não.

Public Shared Function GetBit(ByVal index As Integer) As Integer
        If (PrimosArmazenados(index) = True) Then Return 1 Else Return 0
    End Function

Com isso temos a implementação do algoritmo de Eratosthenes. Basta percorrer o array retornado imprimindo os números primos.

Vejamos agora outro método para calcular números primos.

2-) Usando um algoritmo genérico

Inclua um novo formulário a partir do Menu Project -> Add Windows Forms com o nome de form2.vb e no formulário padrão inclua uma Label , um TextBox, um Button e um ListBox conforme o leiaute abaixo:

A seguir vamos definir o método para calcular números primos chamado  GeraListaNumeroPrimos2() conforme o código abaixo:

Public Class Calculo
    Public Shared Function geraListaNumeroPrimos2(ByVal numeroDeprimos As Int32) As Int32()
        Dim primos(numeroDeprimos - 1) As Int32
        Dim cntr As Int32 = 5
        Dim pcntr As Int32 = 2
        Dim i As Int32
        Dim maxPrimoAoQuadrado As Double
        If numeroDeprimos = 1 Then
            primos(0) = 2
            Return primos
        End If
        If numeroDeprimos = 2 Then
            primos(0) = 2
            primos(1) = 3
            Return primos
        End If
        primos(0) = 2
        primos(1) = 3
        Do Until pcntr = numeroDeprimos
            maxPrimoAoQuadrado = Math.Sqrt(cntr)
            'para cada primo diferente de 2
            For i = 1 To pcntr - 1
                'verifica o resto da divisão
                If cntr Mod primos(i) = 0 Then
                    'NÃO É PRIMO
                    Exit For
                Else
                    'É PRIMO
                    If primos(i + 1) > maxPrimoAoQuadrado OrElse i = pcntr - 1 Then
                        primos(pcntr) = cntr
                        pcntr += 1
                        Exit For
                    End If
                End If
            Next
            cntr += 2
        Loop
        Return primos
    End Function
End Class

O método retorna um array contendo a quantidade de números primos encontrados desejada.

Agora é só alegria...

Vamos testar...

Executando o projeto e testando os dois métodos criados obtemos o seguinte resultado:

Aparentemente nossa implementação funciona mas eu recomendo que se você pretende usar esse código em trabalhos ou em produção que faça testes mais exaustivos para ter certeza de que ele esta realmente funcional.

Pegue o projeto completo aqui: numeroPrimos.zip

Eu sei é apenas VB .NET mas eu gosto...

Referências:


José Carlos Macoratti