Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Sieve of Eratosthenes - Programming in VB

  1. Nov 20, 2003 #1
    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)

    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'.
     
  2. jcsd
  3. Nov 20, 2003 #2

    dduardo

    User Avatar
    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" ;
     
  4. Nov 20, 2003 #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.

    Alright.
     
  5. Nov 20, 2003 #4

    dduardo

    User Avatar
    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"
     
  6. Nov 22, 2003 #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 (Text):

    '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
     
     
  7. Nov 22, 2003 #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.
     
  8. Nov 24, 2003 #7
    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.
     
  9. Nov 24, 2003 #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.
     
  10. Nov 25, 2003 #9
    The status bar sounds interesting. How might I do that?
     
  11. Nov 25, 2003 #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 (Text):

    '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 (Text):

    '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 (Text):

    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.
     
  12. Nov 25, 2003 #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.

     
  13. Nov 25, 2003 #12
    Here is another version I typed out that seems to be not working too:

     
  14. Nov 25, 2003 #13
    Ah! Finally I fixed the program! Thanks for all your help.
     
  15. Feb 28, 2004 #14
    SDNess,

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

    Thanks
     
  16. Feb 28, 2004 #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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Sieve of Eratosthenes - Programming in VB
  1. Need help in vb (Replies: 2)

  2. New to C++ and VB (Replies: 17)

  3. Need help on VB (Replies: 6)

Loading...