VB .NET -
Números Primos (Eratosthenes)
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() |
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 = 8000000A 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