Home Search   What's New Index Books Links Q & A Newsletter Banners   Feedback Tip Jar MSDN Visual Basic Community

Title Make a list of prime numbers in Visual Basic .NET This example shows how to make a list of prime numbers in Visual Basic .NET. primes, prime numbers, sieve, Sieve of Eratosthenes, Euler's Sieve, Legendre, Legendre estimate, prime counting, VB.NET, Visual Basic .NET Algorithms

The Sieve of Eratosthenes is a simple way to make a list of prime numbers. The basic idea is to make an array of numbers. Starting with 2, cross out all multiples of 2 greater than 2. Next cross out all of the multiples of 3 greater than 3.

More generally, find the next number on the list that is not yet crossed out (in this example, 5 would be next) and cross out its multiples after the first one.

Continue until the next prime number p is such that p ^ 2 > the largest number in the list. For example, if you are making a list of prime numbers between 0 and 100, you would cross out multiples of 7 and then stop because the next number not crossed out would be 11 and 11 ^ 2 = 121, which is greater than 100.

Euler noticed an improvement. When you are considering the multiples of the next prime p, you only need to consider numbers that are p * q where q >= p and q ia prime.

For example, when you consider multiples of 7 you would cross out 7 * 7, 7 * 11, 7 * 13, etc. All of the other multiples have already been crossed out.

Any numbers q smaller than 7 were considered when those numbers were considered. For example, 7 * 5 was considered when you crossed out multiples of 5.

Non-prime numbers q bigger than 7 were considered when the factors of those numbers were considered. For example, you crossed out 7 * 21 when you examined multiples of 3.

Enter a value for the largest number to check and click Go. The following code shows how the program works.

```' List primes.
Private Sub btnGo_Click(ByVal sender As System.Object, _
ByVal e As System.EventArgs) Handles btnGo.Click
' Make an array big enough.
Dim max As Integer = Integer.Parse(txtMaxNumber.Text)
Dim is_prime(max) As Boolean

' Assume all of the odd numbers are prime.
' Ignore the even numbers.
For i As Integer = 3 To max Step 2
is_prime(i) = True
Next i

' Use Euler's Sieve.
' See
' http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes.
Dim max_i As Integer = Int(Math.Sqrt(max) + 1)
For i As Integer = 3 To max_i
' Only use i if it is prime.
If (is_prime(i)) Then
' Decide where we need to stop.
Dim max_j As Integer = max \ i
If (max_j Mod 2 = 0) Then max_j -= 1 ' Make it
' odd.

' "Cross out" multiples of i starting
' with i * max_j and ending with i * i.
For j As Integer = max_j To i Step -2
' Only use j if it is prime.
If (is_prime(j)) Then
' "Cross out" i * j.
is_prime(i * j) = False
End If
Next j
End If
Next i

' Display the results.
lstPrimes.Items.Clear()
For i As Integer = 3 To max Step 2
If (is_prime(i)) Then _
Next i

' Display the actual number of primes.
lblActualPrimes.Text = lstPrimes.Items.Count.ToString()

' Display a Legendre estimate ?(n) = n/(log(n) -
' 1.08366).
' See
' http://mathworld.wolfram.com/PrimeCountingFunction.html.
Dim est As Double = max / (Math.Log(max) - 1.08366)
lblEstPrimes.Text = est.ToString("0")
End Sub```