Sieve of Eratosthenes - Programming in VB

In summary: Sieve the numerator and denominator up to the prime number If (Array(x) = 1) Then Seive.AddRow(x, y) Else Seive.AddRow(x, y) End If Next x 'Display the final data in the grid tSeive.Data
  • #1
SDNess
33
0
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:
Computer science news on Phys.org
  • #2
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" ;
 
  • #3
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.
 
  • #4
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"
 
  • #5
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"
        tSeive.Columns.Add(cNumber)
        tSeive.Columns.Add(cPrime)
        Seive.Tables.Add(tSeive)

        '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))
            tSeive.Rows.Add(newRow1)
        Next k

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

    End Sub
 
  • #6
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.
 
  • #7
Wow. Thanks a lot. I will definately 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.
 
  • #8
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.
 
  • #9
The status bar sounds interesting. How might I do that?
 
  • #10
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.
SB1Panel1.Text = "Ready..."
' 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(SB1Panel1)
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
        SB1Panel1.Text = "Ready..."
        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
        SB1Panel1.Text = "Ready..."
        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.
 
  • #11
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
 
  • #12
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
lstPrimes.AddItem z
End If
Next z
End Sub

Private Sub Form_Load()
n = 100
End Sub

Private Sub txtn()
n = Val(txtn)
End Sub
 
  • #13
Ah! Finally I fixed the program! Thanks for all your help.
 
  • #14
SDNess,

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

Thanks
 
  • #15
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.
 

What is the Sieve of Eratosthenes algorithm?

The Sieve of Eratosthenes is a mathematical algorithm used to find all prime numbers up to a given limit. It works by creating a list of all numbers from 2 to the limit, and then crossing off all multiples of each number starting with 2. This process is repeated until all numbers have been checked, leaving behind only the prime numbers.

How does the Sieve of Eratosthenes work in programming?

In programming, the Sieve of Eratosthenes is implemented using loops and arrays. The algorithm can be broken down into the following steps:

  1. Create a list of numbers from 2 to the given limit.
  2. Start with the first number in the list, which is 2.
  3. Cross off all multiples of 2 in the list.
  4. Move on to the next number in the list that has not been crossed off.
  5. Repeat steps 3 and 4 until all numbers have been checked.
  6. The remaining numbers in the list are the prime numbers.

What are the advantages of using the Sieve of Eratosthenes algorithm?

The Sieve of Eratosthenes is a fast and efficient way to find all prime numbers up to a given limit. It is also relatively easy to implement in programming and can handle large numbers without taking up too much memory. Additionally, the algorithm can be modified to find prime numbers in a specific range, making it versatile for different applications.

Are there any limitations to the Sieve of Eratosthenes algorithm?

While the Sieve of Eratosthenes is a useful algorithm for finding prime numbers, it does have some limitations. It can become less efficient when dealing with very large numbers, as the list of numbers to check becomes longer. It also requires storing all numbers up to the given limit in memory, which can be a limitation for certain applications.

Can the Sieve of Eratosthenes be used for other mathematical problems?

Yes, the Sieve of Eratosthenes has been adapted for use in other mathematical problems such as finding twin primes (pairs of primes that differ by 2) and prime quadruplets (sets of four primes that differ by 2). It can also be used to solve problems related to factorization and finding highly divisible numbers.

Similar threads

  • Computing and Technology
Replies
20
Views
2K
Replies
1
Views
932
Replies
6
Views
1K
Replies
8
Views
1K
Replies
1
Views
2K
Replies
5
Views
2K
  • Programming and Computer Science
Replies
16
Views
1K
  • Linear and Abstract Algebra
Replies
2
Views
705
  • Calculus and Beyond Homework Help
Replies
3
Views
692
Back
Top