# Sieve of Eratosthenes - Programming in VB

## Main Question or Discussion Point

I am trying to program the 'sieve of eratosthenes' in visual basic. For those that don't know, it is an algorithm for making tables of primes. Sequentially write down the integers from 2 to the highest number n you wish to include in the table. Cross out all numbers which are divisible by 2 (every second number). Find the smallest remaining number . It is 3. So cross out all numbers which are divisible by 3 (every third number). Find the smallest remaining number . It is 5. So cross out all numbers which are divisible by 5 (every fifth number). Continue until you have crossed out all numbers divisible by , where is the floor function. The numbers remaining are prime. This procedure is illustrated in the above diagram which sieves up to 50, and therefore crosses out primes up to . If the procedure is then continued up to n, then the number of cross-outs gives the number of distinct prime factors of each number. (http://mathworld.wolfram.com/EratosthenesSieve.html [Broken])

I have some code. But how would you go about programming this? I have psuedocode in front of me and forgot to e-mail my other files to myself, but I will try to post what I have so far in the near future.

I was thinking about doing it with listboxes, arrays, and 'for loops'.

Last edited by a moderator:

Related Computing and Technology News on Phys.org
dduardo
Staff Emeritus
How big of a prime do you want to get?

The simplest and most logical way of going about it is to create a HUGE array with an intial value of 1. Then you would have a loop to traverse the array and set the position to 0 to cancel it out.

Here is the basic setup in c++. I'm pretty sure you can convert this to vb

#define SIZE 10000

bool array[SIZE] ;

for( int x = 0 ; x < SIZE ; x++ )
array[SIZE] = 1 ;

for( int x = 2 ; x < SIZE ; x++ )
for( int y = x-1 ; y<SIZE ; y += x )
if( y != x-1 )
array[y] = 0 ;

for( int x = 0 ; x < SIZE ; x++ )
if( array[x] == 1 )
cout << x+1 << " is a prime number\n" ;

I am not that familiar with C++. I might be able to convert it, but if you have time please do.

My start number will be 2 and end number being huge. It should work with all end numbers typed into the input.

The simplest and most logical way of going about it is to create a HUGE array with an intial value of 1. Then you would have a loop to traverse the array and set the position to 0 to cancel it out.
Alright.

dduardo
Staff Emeritus
Argh, I don't program in vb. Here is an attempt at vb from a quick glance at an online tutorial. If it doesn't work, its not my fault. Learn C++.

Dim size As Integer
Get size

Dim array(size) As Integer

For x = 1 To size
array(x) = 1
Next

For x = 2 To size
For y = x To size Step x
If y <> x Then
array(x) = 0
End If
Next
Next

For x = 1 To size
if array(x) = 1 Then
Print x
Print " is a prime number"

I couldn't get your algorithm to work properly dduardo, probably me. So I altered it a little, and added code to display the final data in a datagrid, which allows easy viewing. Here is the code, (to use simply create a new windows application, and add a datagrid to the form. Note this was tested on VB.NET, not sure if the code would be identical for earlier version of VB, but try it if you have an earlier version.):

Code:
'Create Array, and variable to hold ceiling size
'This code goes in the global declarations section
Dim numsize As Integer
Dim numarray() As Integer

'Create dataset, datatable, datacolumns etc
'This also goes in the global declarations section
Dim Seive As New DataSet("SeiveSet")
Dim tSeive As New DataTable("SeiveTable")
Dim cNumber As New DataColumn("Number", GetType(Integer))
Dim cPrime As New DataColumn("Prime", GetType(Boolean))

Private Sub Form1_Load(ByVal sender As System.Object, ByVal e As_ System.EventArgs) Handles MyBase.Load
Dim i As Integer
'Get the user to provide the ceiling
numsize = CInt(InputBox("Input the Ceiling_
Number: ", "Define Ceiling", 1))

'Initialize the array
ReDim numarray(numsize)
For i = 0 To (numsize - 1)
numarray(i) = 1
Next i

'Run the algorithm
Dim x, y As Integer
For x = 2 To numsize
For y = x + 1 To numsize
If y Mod x = 0 Then
numarray(y - 1) = 0
End If
Next y
Next x

'Send the array data to the dataset
SetupDataSet()

End Sub

Private Sub SetupDataSet()

'Setup the DataSet
DataGrid1.CaptionText = "Seive of Eratosthenes"

'Input the data into the dataset
Dim newRow1 As DataRow
Dim k As Integer
For k = 0 To (numsize - 1)
newRow1 = tSeive.NewRow()
newRow1("Number") = k + 1
newRow1("Prime") = CBool(numarray(k))
Next k

'Bind the dataset to a datagrid
DataGrid1.SetDataBinding(Seive, "SeiveTable")

End Sub

Thinking about it, if you are working with really large numbers, you may want to remove the initialization code from the form_load section and into a sub of its own, which you can call from form_load. This will allow the form to load properly, also add an "application.doevents" line into each for next loop, or your computer may hang while the code executes. If you feel like may also which to consider adding a status bar and adding code to tell you how the program is fairing, this is VERY useful for large code execution to tell you whether the prog has crashed, or is doing its job properly.

Wow. Thanks a lot. I will definetly take that into consideration. I hate to be picky, but if I want to convert the data grids into listboxes I would just replace them respectively. I am not familiar with datagrids yet and am still learning the functions of the listboxes so I want to keep it as concentrated as possible and make sure I know what i am doing.

Yeah if you want to use list boxes just ignore all the code for datagrids, and keep all the math code. Then just fill a list box with the array data.

The status bar sounds interesting. How might I do that?

Well to create a status bar is the easy bit. You simply drag a statusbar onto your form. Let's suppose for the moment you name the statusbar, SB1. The status bar will sit at the bottom of the form. Now we need to add some panels to the status bar so that we can display information. In the global declarations section of your code (where you should have created you array), add this code:

Code:
'Create Two StatusBar Panels
dim Panel1 as new StatusBarPanel()
dim Panel2 as new StatusBarPanel()
You can add more panels if you'd like to. Now we need to set up the properties of the panels, which we add to the form_load sub:

Code:
'Set the text property of the statusbar to nothing.
SB1.text=nothing
' Display the first panel with a sunken border style.
SB1Panel1.BorderStyle = StatusBarPanelBorderStyle.Sunken
' Initialize the text of the panel.
' Set the AutoSize property to use all remaining space on SBar.
SB1Panel1.AutoSize = StatusBarPanelAutoSize.Spring
' Display the second panel with a raised border style.
SB1Panel2.BorderStyle = StatusBarPanelBorderStyle.Sunken
' Set the AutoSize property to size the panel to contents size.
SB1Panel2.AutoSize = StatusBarPanelAutoSize.Spring
' Display panels in the StatusBar control.
SB1.ShowPanels = True
' Add both panels to the StatusBarPanelCollection of SBar.
SB1.Panels.Add(SB1Panel2)
Now that looks like a lot of code, but you could equally change it all using the properties menu if you'd prefer, thus removing all that code. Also you can look all the information up using the index, which is a wonderful tool for learning all the tricks of the trade.

Basically all I've done so far is add two panels to the status bar at the bottom of the form. Those panels will be used to display information.

Now the useful bit. (And probably the easiest bit code wise). Whenever you have a loop (Like the for loops in the sieve code), simply set use panel1 to explain what is going on, and panel two to keep a running percentage on the loop. Here's and example, it uses the Initialise code above:

Code:
Private Sub Initialize()
Dim i As Integer
Dim j As Decimal
'Initialize the array
ReDim numarray(numsize)
SB1Panel1.Text = "Setting Up Array..."
For i = 0 To (numsize - 1)
Application.DoEvents()
j = 100 * (i / (numsize - 1))
j = j.Round(j, 0)
SB1Panel2.Text = CStr(j) & "%"
numarray(i) = 1
Next i
SB1Panel2.Text = Nothing

'Run the algorithm
Dim x, y As Integer
SB1Panel1.Text = "Running..."
For x = 2 To numsize
For y = x + 1 To numsize
Application.DoEvents()
j = 100 * (x / numsize)
j = j.Round(j, 0)
SB1Panel2.Text = CStr(j) & "%"
If y Mod x = 0 Then
numarray(y - 1) = 0
End If
Next y
Next x
SB1Panel2.Text = Nothing
End Sub
The above code keeps the user up to speed with what is going on, and as I said is most useful for determining how a program is running. It may seem like a lot of code, but it is useful to learn.

Ugg...I'm having some problems with converting the listboxes and stuff. I'm trying to form my own code out of this too and have so many different projects open I'm getting confused. I have also added a search function to the project also. Here's my code so far...some of might be confusing.

Dim numsize As Integer
Dim numarray As Integer

Private Sub cmdFind_Click()
Dim intX As Integer
Dim intStartNumber As Integer
Dim intEndNumber As Integer

intStartNumber = 2
intEndNumber = Val(txtEndNumber)

Dim i As Integer
'Get the user to provide the ceiling
numsize = CInt(InputBox("Input the Ceiling Number: ", "Define Ceiling", 1))

'Initialize the array
ReDim numarray(numsize)
For i = 0 To (numsize - 1)
numarray(i) = 1
Next i

'Run the algorithm
Dim x, y As Integer
For x = 2 To numsize
For y = x + 1 To numsize
If y Mod x = 0 Then
numarray(y - 1) = 0
End If
Next y
Next x

'Send the array data to the dataset

End Sub

Private Sub cmdSearch_Click()

Dim intSearchKey As Integer
intSearchKey = Val(txtSearchKey)
Dim intListNumber As Integer

For intListNumber = 0 To lstList1.ListCount - 1 Step 1
If intSearchKey = lstSquares.List(intListNumber) Then
MsgBox "Weve Found Our Number"
End If
Next

End Sub

Here is another version I typed out that seems to be not working too:

Option Explicit
Dim n As Long
Dim y As Long
Dim x As Long
Dim z As Long
Dim lngNumArray(210000) As Long

'Const stepindMAX As Long = 10000
'Dim primes() As Long
'Dim indPrimes As Long
'Dim indMAX As Long

Private Sub cmdCalculate_Click()

Dim i As Long
Dim s As String

indPrimes = 1
indMAX = stepIndMAX
ReDim primes(1 To indMAX) As Long
primes(1) = 1
lstPrimes.Text = "Computing"
For i = 2 To Val(txtInput.Text)
If IsPrime(i) Then
indPrimes = indPrimes + 1

If indPrimes > indMAX Then

indMAX = indMAX + stepIndMAX
ReDim Preserve primes(1 To indMAX) As Long
DoEvents
If stopCalculus Then
lockCalculus = False
Exit Sub
End If
End If

primes(indPrimes) = i
End If
Next

lstPrimes.Text = "Storing file : primes.txt"

For i = 1 To indPrimes
DoEvents
If stopCalculus Then
lstPrimes.Text = "Storing file : stopped"
lockCalculus = False
Exit Sub
End If
Next
lstPrimes.Text = "Storing file : complete" & vbCrLf & "Generating list"

For i = 1 To indPrimes
DoEvents
s = s + Str(primes(i)) + vbCrLf
If stopCalculus Then
lstPrimes.Text = "Storing file : complete" & vbCrLf & "Generating list: stopped"
lockCalculus = False
Exit Sub
End If
Next
lstPrimes.Text = s

lockCalculus = False

End Sub

Function IsPrime(n As Long) As Boolean

Dim i As Long
Dim root As Long
root = Sqr(n)
For i = 2 To indPrimes
If primes(i) <= root Then
If (n Mod primes(i)) = 0 Then
IsPrime = False
Exit Function
End If
Else
IsPrime = True
Exit Function
End If
Next
IsPrime = True
End Function

Private Sub cmdPrime_Click()

For x = 2 To n Step 1
lngNumArray(x) = 1
Next x

For x = 2 To 0.5 * n Step 1
If lngNumArray(x) = 1 Then
For y = x + 1 To n Step 1
If y Mod x = 0 Then
lngNumArray(y) = 0
End If
Next y
End If
Next x

For z = 0 To n Step 1
If lngNumArray(z) - 1 Then
End If
Next z
End Sub

n = 100
End Sub

Private Sub txtn()
n = Val(txtn)
End Sub

Ah! Finally I fixed the program! Thanks for all your help.

SDNess,

I am trying to fix your posted code without good results. Could you please post your fixed version of the code?

Thanks

Hmm...I'm having trouble finding the file on my computer...I had A LOT of SoE files. I'll check at school on Monday and see if it's on that computer.