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 cmdListPrimes_Click()
Dim max As Integer
Dim is_prime() As Boolean
Dim i As Integer
Dim j As Integer
Dim max_i As Integer
Dim max_j As Integer
Dim est As Double

        ' Make an array big enough.
        max = Val(txtMaxNumber.Text)
        ReDim is_prime(0 To max)

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

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

                ' "Cross out" multiples of i starting
                ' with i * max_j and ending with i * i.
                For j = 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.Clear
        lstPrimes.AddItem "2"
        For i = 3 To max Step 2
            If (is_prime(i)) Then lstPrimes.AddItem i
        Next i

        ' Display the actual number of primes.
        txtActualPrimes.Text = Format$(lstPrimes.ListCount)

        ' Display a Legendre estimate ?(n) = n/(log(n) -
        ' 1.08366).
        ' See
        ' http://mathworld.wolfram.com/PrimeCountingFunction.html.
        est = max / (Log(max) - 1.08366)
        txtEstPrimes.Text = Format$(est, "0")
End Sub