Visual Basic 2010 (Console) Guide
Bit Arrays

A BitArray is a compact array of bits where each element is represented by a boolean value, where true indicates an on bit and false an off bit.

We can use this structure to implement an ancient techinique for finding prime numbers called the Sieve of Eratosthenes.

The principle is that we start with a super huge array of bits. We want the bit to be set to true if the number is prime, false if not. The program starts by declaring the BitArray with all of its elements set to true. The first value is read and, if true, all multiples of that value in the array are set to false, since they cannot be prime. The next number is then read and the process completed until this has been done with all numbers. Anything still set to true is prime.

The program has been written using procedures and functions to keep it tidy. A wee menu type interface is provided for the user. Apart from crashes when incorrect data types are entered, this program runs in a continual loop until the user chooses to quit.

Const maxNumber As Integer = 8000000
Dim primeStore As BitArray = New BitArray(maxNumber, True)

Sub Main()
   Sieve()
   Dim numCheck As Integer
   While GetMenuChoice() = 1
      numCheck = ReadNumber()
      CheckNumber(numCheck)
   End While
End Sub

Function GetMenuChoice() As Integer
   Console.Clear()
   Console.WriteLine("Sieve Of Eratosthenes: Menu")
   Console.WriteLine("***************************")
   Console.WriteLine()
   Console.WriteLine("1. Test A Number")
   Console.WriteLine("2. Quit The Program")
   Console.WriteLine()
   Console.Write("Enter your choice: ")
   Dim intchoice As Integer
   intchoice = Console.ReadLine()
   Return intchoice
End Function

Function ReadNumber() As Integer
   Console.Clear()
   Console.Write("Enter your number: ")
   Dim intNum As Integer
   intNum = Console.ReadLine()
   Return intNum
End Function

Sub CheckNumber(ByVal num As Integer)
   If primeStore(num) = True Then
      Console.WriteLine("{0} is prime", num)
   Else
      Console.WriteLine("{0} is not prime", num)
   End If
   Console.WriteLine()
   Console.WriteLine("Press Enter")
   Console.ReadLine()
End Sub

Sub Sieve()
   Dim index As Integer = 1
   While (index < maxNumber - 1)
      index = index + 1
      If primeStore(index) = True Then
         For count = index * 2 To maxNumber - 1 Step index
            primeStore(count) = False
         Next
      End If
   End While
End Sub

Having A Go

  1. Add the necessary code to the program to output all of the prime numbers lower than the maxNumber constant.