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()
    lstPrimes.Items.Add("2")
    For i As Integer = 3 To max Step 2
        If (is_prime(i)) Then _
            lstPrimes.Items.Add(i.ToString())
    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