Using A Loop/Array To Find Prime Numbers

  • (2 Pages)
  • +
  • 1
  • 2

19 Replies - 16299 Views - Last Post: 10 October 2012 - 02:21 PM Rate Topic: -----

#1 CodyMcCoderson  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 08-October 12

Using A Loop/Array To Find Prime Numbers

Posted 08 October 2012 - 06:34 PM

Hey Everyone.

Im new here, read over all the do's and dont's and I believe I can abide by these, so lets give'r a go.
I found this website, and as I am taking a programming course right now, Im hoping I can pick everyones brain to give me a hand as its not my strong suit, but once im steered in the right direction I usually grasp things very quickly.

Im currently working on a homework assignment for my programming class, and Ive come across a part of a question that is making me want to put my head through a wall. Any help would be great. I dont expect the code to fix the problem, but any hints or tips to get me in the right direction would be wonderful.

So, here is the question at hand.
I need my code to take any given number that has been entered, and output all of the PRIME numbers up to and including the number entered.

I have like 200 lines of me trying many different things, and this one seems to be (in my head) the closest I have to a working code.

Module Module1


    Sub Main()
        Dim i As Integer
        Dim x As Integer
        Dim num1 As Integer
        Dim N As Integer
        Dim c As Integer
        c = 0

        Console.WriteLine("Please enter a number: ")
        num1 = Console.ReadLine()


        For i = 1 To num1 \ 2
            If num1 Mod i = 0 Then c = c + 1 'how do i add to list
        Next

        Console.WriteLine("Here are the prime numbers up to " & num1)

        'For x = 1 To num1.Length - 1
        num1 = Integer.Parse(Console.ReadLine)
        If x Mod N >= 1 Then
            'Exit For

        ElseIf x Mod N = 0 Then 'add to list


        End If
        Console.ReadLine()


        Console.ReadLine() 'keeps the window open
    End Sub
End Module



Is This A Good Question/Topic? 0
  • +

Replies To: Using A Loop/Array To Find Prime Numbers

#2 lar3ry  Icon User is offline

  • Coding Geezer
  • member icon

Reputation: 310
  • View blog
  • Posts: 1,290
  • Joined: 12-September 12

Re: Using A Loop/Array To Find Prime Numbers

Posted 08 October 2012 - 09:37 PM

View PostCodyMcCoderson, on 08 October 2012 - 06:34 PM, said:

I need my code to take any given number that has been entered, and output all of the PRIME numbers up to and including the number entered.

I have like 200 lines of me trying many different things, and this one seems to be (in my head) the closest I have to a working code.


Is it a requirement of the homework assignment to use an array? If not, You might want to think about whether or not you need one.

Now, here's the thing about writing a program: first thing is to have a plan. Write an outline describing, in broad terms, what you want to do, then take each part of the outline and think about ways to implement that plan. Keep doing this, getting more specific at each stage.

Once you have a plan, start writing code for each of the tasks.
Once you have code for one task, test it.
The best way to test is to debug the program with example data, using the tools that Visual Studio has so thoughtfully provided, like breakpoints, single-stepping through the code, and the ability to see the contents of your variables.

As you step through the code and check the variable contents, ask yourself what should be happening. If you think a variable should contain, for example, a value of 2, and it doesn't, stop right there and try to figure out why it differs from the expected value. Let's have a look at the first part of your code from a testing perspective.

Quote

Module Module1
    Sub Main()
        Dim i As Integer
        Dim x As Integer
        Dim num1 As Integer
        Dim N As Integer
        Dim c As Integer
        c = 0

        Console.WriteLine("Please enter a number: ")
        num1 = Console.ReadLine()


The first thing to consider is your choice of variable names. None of these are meaningful in terms of what they are meant to hold. Instead of num1, why not use something that tells you it's the input number, or the maximum size of the primes you are looking for.. inputNum or maxTest, for example. It is far to easy to make mistakes when you forget, in the middle of writing code, which variable you used to hold a particular value.

For testing purposes, you might want to replace the Console.WriteLine and Console.readLine with
      num1 = 20


This lets you test quickly, and always with the same data, for ease of troubleshooting.
Later, you should revert to the Console operations to try many different values to make sure your code works for more than just one input value.

Quote

        For i = 1 To num1 \ 2
            If num1 Mod i = 0 Then c = c + 1 'how do i add to list
        Next



This is a good place to start planning AND troubleshooting. What is the purpose of this loop? Do you really want to do what it actually is doing?

If you place a breakpoint on the line with the If statement, and run your program, it will stop on that line. Single-stepping will show that the If will be true, and you will add 1 to the variable c. keep single-stepping, and you will find out what is wrong with your logic.

There are many more errors in logic in your code. Again, try to break the project into small tasks, and write code for each task, testing as you go along.

As for your question about a list, by which I believe you mean an array, you first need to declare an array, dimension it, and decide what sort of data it will hold. Then you place values into it using an index variable. Think carefully about what you want the array to contain. In the case of your first For loop, it looks like you wanted it to hold all non-prime numbers up to half the input number.

Give these ideas a try and let us know how it's going.

This post has been edited by lar3ry: 08 October 2012 - 09:39 PM

Was This Post Helpful? 0
  • +
  • -

#3 November-06  Icon User is offline

  • D.I.C Regular

Reputation: 46
  • View blog
  • Posts: 396
  • Joined: 04-January 11

Re: Using A Loop/Array To Find Prime Numbers

Posted 08 October 2012 - 11:24 PM

I am not sure if there is an even simpler way to do this... Anyway, here's my code...

Private Sub PrimeFactors()
        Dim intInput As Integer = 45
        Dim strFactorEquation As String = String.Empty
        'Even without array, you can display the factors

        While intInput <> 1
            For i = 2 To intInput
                'Check if i is a factor of the entered number
                If intInput Mod i = 0 Then
                    'Check if i is a prime factor
                    If IsPrime(i) Then
                        If strFactorEquation <> String.Empty Then
                            strFactorEquation &= "*"
                        End If
                        strFactorEquation &= i
                        intInput = intInput / i
                        Exit For
                    End If
                End If
            Next
        End While

        'From the strFactorEquation, if you really need an array, you can insert it to an array by splitting the * symbol
        Dim strPrimeFactors As String() = strFactorEquation.Split("*"c)

        Console.Write(strFactorEquation)
        Console.ReadLine()
    End Sub

    Private Function IsPrime(ByVal intInput As Integer) As String
        For i = 2 To intInput - 1
            If intInput Mod i = 0 Then
                Return False
            End If
        Next
        Return True
    End Function


Was This Post Helpful? 0
  • +
  • -

#4 lar3ry  Icon User is offline

  • Coding Geezer
  • member icon

Reputation: 310
  • View blog
  • Posts: 1,290
  • Joined: 12-September 12

Re: Using A Loop/Array To Find Prime Numbers

Posted 08 October 2012 - 11:44 PM

Actually, he wasn't trying to find the prime factors of the input number, but rather all the prime numbers up to and including the input number.

I really didn't want to do his homework for him, as I would rather help him understand the process and techniques involved in writing a program.

But if we're doing his homework for him, maybe I should just post my code.
Was This Post Helpful? 0
  • +
  • -

#5 CodyMcCoderson  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 08-October 12

Re: Using A Loop/Array To Find Prime Numbers

Posted 09 October 2012 - 04:38 AM

View Postlar3ry, on 08 October 2012 - 11:44 PM, said:

Actually, he wasn't trying to find the prime factors of the input number, but rather all the prime numbers up to and including the input number.

I really didn't want to do his homework for him, as I would rather help him understand the process and techniques involved in writing a program.

But if we're doing his homework for him, maybe I should just post my code.


Thanks for the tips in your first post.

I believe the main problem im having is getting the correct equation to figure out the prime of 1 number, and then for it to continually loop down 1 number every time until the end.

As for your question on if an array is needed, no. I dont believe it is.
Was This Post Helpful? 0
  • +
  • -

#6 lar3ry  Icon User is offline

  • Coding Geezer
  • member icon

Reputation: 310
  • View blog
  • Posts: 1,290
  • Joined: 12-September 12

Re: Using A Loop/Array To Find Prime Numbers

Posted 09 October 2012 - 07:19 AM

View PostCodyMcCoderson, on 09 October 2012 - 04:38 AM, said:

I believe the main problem im having is getting the correct equation to figure out the prime of 1 number, and then for it to continually loop down 1 number every time until the end.

Exactly right.
I made a form with one single-line TextBox, one multi-line TextBox, and a Button. You can place a default value in the single-line TextBox so you don't have to keep entering it when you test.

So, let's first have a look at deciding which numbers to test.
Let's call the number to be tested testNum.

A prime number is any number greater than 1 that is evenly divisible by 1 or itself.

Right away, we can see that 1 is not prime, and 2 is prime pretty much by definition, so we could just write them out to the console (I prefer a TextBox), but that seems like a bit of a cheat to me, so let's create a function called isPrime, and call it with 1. Then with 2. The reason for this is that

1. we want to follow the requirements of the task, and 1 and 2 are required to be shown
2. we might want to use this code in another program, so our isPrime function should handle all cases
3. even numbers are never prime, so we can use a bit of a shortcut in our loop to generate testNum values.

    Private Sub Button1_Click(sender As System.Object, e As System.EventArgs) Handles Button1.Click
        Dim inputNum As Integer = CInt(TextBox1.Text)
        Dim i As Integer = 1
        TextBox2.Clear()
        If isPrime(i) Then TextBox2.Text = i & vbNewLine
        i += 1
        If isPrime(i) Then TextBox2.Text &= i & vbNewLine

       'For loop here. bearing in mind the comments about which numbers to test,
       'decide what number to start with and how the loop counter should increment
       'place a call to isPrime inside the loop
       'is isPrime returns True, show it in TextBox 2

    End Sub

    Private Function isPrime(ByVal testnum As Integer) As Boolean
        isPrime = False
        If testnum = 1 Then Return False
        If testnum = 2 Then Return True
        If testnum Mod 2 = 0 Then Return False

        'we'll complete this later. for now, it will only test for 1, 2 and even numbers

    End Function



See what you can come up with for the calling loop, and take a crack at a loop to test the number in isPrime().
Was This Post Helpful? 1
  • +
  • -

#7 CodyMcCoderson  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 08-October 12

Re: Using A Loop/Array To Find Prime Numbers

Posted 09 October 2012 - 09:52 AM

Okay, Ive cleaned it up, and I believe im 1 or 2 steps away from completing this.

    Sub Main()
        Dim inputNum As Integer
        Dim isPrime As Boolean = False

        Console.WriteLine("Please enter a number: ")
        inputNum = Console.ReadLine()

        Dim primeNumbers As String = ""
        For c As Integer = 2 To (inputNum - 1)
            If inputNum Mod c = 0 Then ''If inputNum - c Mod c = 0 Then
                primeNumbers += c & ","
            End If
            'For x As Integer = 3 To (inputNum - 1)
            '    If inputNum Mod 3 = 0 Then
            '        primeNumbers = c & ","
            '    End If
            'Next
        Next
        Console.WriteLine("Here are the prime numbers up to " & inputNum)
        Console.WriteLine(primeNumbers)



Basically I can get the factors of any given number, now I need to find prime numbers.
I hope im heading in the right direction. And you're helping me a ton right lar3ry now by giving me ideas.

I know I need another for loop within the one I have, Im just struggling with the math on finding the primes instead of the factors.
Was This Post Helpful? 0
  • +
  • -

#8 lar3ry  Icon User is offline

  • Coding Geezer
  • member icon

Reputation: 310
  • View blog
  • Posts: 1,290
  • Joined: 12-September 12

Re: Using A Loop/Array To Find Prime Numbers

Posted 09 October 2012 - 11:00 AM

You're getting there, but there are a few things first...

You probably should write isPrime as a function. That way it is encapsulated, and you can concentrate on two separate, smaller tasks. The first is calling it, and the second is determining if it's prime. If you haven't used functions before, they may be a little intimidating, but really they are just an encapsulation of code to do one small task. In my example program, there are only a few checks for primality, but the next bit to be added to it is really not overly long or complex. Functions may be thoroughly tested by calling them with test data, and once it is debugged, you can completely ignore it and just call it, in the same way you might call MessageBox, where you are not concerned with how it's done in the function, just that it works.

In fact, why not start a new project (call it Test or PrimeTest or whatever), with a form, the two TextBoxes and one button that I mentioned before, and just paste in the code I supplied, and we can develop the rest in unison. Once it's running, you can easily change over to whatever form of input and output you want.

Quote

Sub Main()
    Dim primeNumbers As String = ""
    For c As Integer = 2 To (inputNum - 1)
        If inputNum Mod c = 0 Then ''If inputNum - c Mod c = 0 Then
            primeNumbers += c & ","
        End If



As you pointed out, this finds the factors of the input number.
Try removing your 'Dim isPrime ...' statement, and change the If to:

       If isPrime(c)    'assuming you have a function called isPrime()
           primenumbers += c & ","
       End If



This will call isPrime for all the values of c, but of course we haven't done everything in isPrime yet. But it will let you test the logic of the calls to isPrime.

Quote

[code
'For x As Integer = 3 To (inputNum - 1)
' If ... Then
' ...
' End If
'Next
Next
[/code]


This is something like what you want in the isPrime() function, but leave that for now.
Please make that test project. It will be much easier, and less error-prone to work on the same code together.
Was This Post Helpful? 0
  • +
  • -

#9 CodyMcCoderson  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 08-October 12

Re: Using A Loop/Array To Find Prime Numbers

Posted 09 October 2012 - 11:59 AM

Ive never worked with text boxes or anything.
I have the code, but its in a console app as thats all we've been working with.
Was This Post Helpful? 0
  • +
  • -

#10 lar3ry  Icon User is offline

  • Coding Geezer
  • member icon

Reputation: 310
  • View blog
  • Posts: 1,290
  • Joined: 12-September 12

Re: Using A Loop/Array To Find Prime Numbers

Posted 09 October 2012 - 01:27 PM

View PostCodyMcCoderson, on 09 October 2012 - 11:59 AM, said:

Ive never worked with text boxes or anything.
I have the code, but its in a console app as thats all we've been working with.

OK... fair enough. Here's a rewrite into a console application, again not complete, so we can do a little thinking.
Paste this between the Module and End Module statements:
    Dim inputNum As String = 0

    Sub Main()
        Dim primeNumbers As String
        Do While inputNum <> "end"
            Console.WriteLine(vbNewLine & "Please enter a number: ( 'end' to stop)")
            primeNumbers = ""
            inputNum = Console.ReadLine()
            If inputNum = "end" Then End
            Dim i As Integer = 1
            If isPrime(i) Then primeNumbers = i
            i += 1
            If isPrime(i) Then primeNumbers = i
            For i = 3 To inputNum 'not inputNum-1, because we want to test inputNum as well
                If isPrime(i) Then
                    primeNumbers &= "," & i
                End If
            Next
            Console.WriteLine(vbNewLine & "Prime numbers up to " & inputNum)
            Console.WriteLine(primeNumbers)
        Loop
    End Sub

    Private Function isPrime(ByVal testnum As Integer) As Boolean
        Dim ctr As Integer
        If testnum = 1 Then Return False
        If testnum = 2 Then Return True
        If testnum Mod 2 = 0 Then Return False
        isPrime = True
        'For loop goes here.... 
        'Again, try to figure out what should go in the first line of the loop
        'then what goes into the inner part of the loop.
    End Function


You'll notice that if you run this, you'll get erroneous results (like 9 being a prime), but at least you'll have tested the call logic.

Let us know when you have that running.

This post has been edited by lar3ry: 09 October 2012 - 01:29 PM

Was This Post Helpful? 1
  • +
  • -

#11 CodyMcCoderson  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 30
  • Joined: 08-October 12

Re: Using A Loop/Array To Find Prime Numbers

Posted 09 October 2012 - 01:50 PM

Got it, and tried a couple things. I put [[?]] around the questions for you to see where I was working.
Im so new to this so im still trying to wrap my head around everything along with juggling 5 other classes.

Module Module1
    Dim inputNum As String = 0

    Sub Main()
        Dim primeNumbers As String
        Do While inputNum <> "end"
            Console.WriteLine(vbNewLine & "Please enter a number: ( 'end' to stop)")
            primeNumbers = ""
            inputNum = Console.ReadLine()
            If inputNum = "end" Then End
            Dim i As Integer = 1
            If isPrime(i) Then primeNumbers = i
            i += 1
            If isPrime(i) Then primeNumbers = i
            For i = 3 To inputNum 'not inputNum-1, because we want to test inputNum as well '[[?]]'Would this be step 1 If I want to check all numbers to the inputNum?[[?]]
                If isPrime(i) Then
                    primeNumbers &= "," & i
                End If
            Next
            Console.WriteLine(vbNewLine & "Prime numbers up to " & inputNum)
            Console.WriteLine(primeNumbers)
        Loop
    End Sub

    Private Function isPrime(ByVal testnum As Integer) As Boolean
        Dim ctr As Integer
        If testnum = 1 Then Return False
        If testnum = 2 Then Return True
        If testnum Mod 2 = 0 Then Return False
        isPrime = True
        'For loop goes here.... 
        For ctr = inputNum To 0 Step -1
            '[[?]]inputNum mod ? I dont know what i should mod here, or even if I should mod.[[?]]
        Next
        'Again, try to figure out what should go in the first line of the loop
        'then what goes into the inner part of the loop.
    End Function

End Module


Was This Post Helpful? 0
  • +
  • -

#12 DimitriV  Icon User is offline

  • They don't think it be like it is, but it do
  • member icon

Reputation: 584
  • View blog
  • Posts: 2,738
  • Joined: 24-July 11

Re: Using A Loop/Array To Find Prime Numbers

Posted 09 October 2012 - 01:54 PM

I think maybe inputNum Mod ctr. However, inputNum should only be tested from half of its value downwards.
Was This Post Helpful? 0
  • +
  • -

#13 lar3ry  Icon User is offline

  • Coding Geezer
  • member icon

Reputation: 310
  • View blog
  • Posts: 1,290
  • Joined: 12-September 12

Re: Using A Loop/Array To Find Prime Numbers

Posted 09 October 2012 - 02:00 PM

View PostDimitriV, on 09 October 2012 - 01:54 PM, said:

I think maybe inputNum Mod ctr. However, inputNum should only be tested from half of its value downwards.

Actually, it wil be testnum mod ctr.

Patience, DimitriV, that loop wil be refined later in the lesson.
Was This Post Helpful? 0
  • +
  • -

#14 DimitriV  Icon User is offline

  • They don't think it be like it is, but it do
  • member icon

Reputation: 584
  • View blog
  • Posts: 2,738
  • Joined: 24-July 11

Re: Using A Loop/Array To Find Prime Numbers

Posted 09 October 2012 - 02:02 PM

Thanks, lar3ry.
Was This Post Helpful? 0
  • +
  • -

#15 lar3ry  Icon User is offline

  • Coding Geezer
  • member icon

Reputation: 310
  • View blog
  • Posts: 1,290
  • Joined: 12-September 12

Re: Using A Loop/Array To Find Prime Numbers

Posted 09 October 2012 - 02:29 PM

View PostCodyMcCoderson, on 09 October 2012 - 01:50 PM, said:

[[?]]'Would this be step 1 If I want to check all numbers to the inputNum?[[?]]


Yes it would, but that's the default for the For/Next loop. It's only if you want to step by something other than +1 that you need to specify a Step value.

Quote

[[?]]inputNum mod ? I dont know what i should mod here, or even if I should mod.[[?]]

Close! But we are not testing InputNum. Notice the calls to isPrime(). In all cases we are calling it with a parameter of (i). In the first call, i = 1. We then add 1 to i, making it = 2, and call isPrime with that value. At this point, we have tested the first two numbers between 1 and inputNum.

We then use a For/Next loop that increments i from 3 through inputNum, and call isPrime(i), testing every number between 3 and inputNum inclusive.

Now, here's a little trick we can use to refine the calling loop. It isn't necessary, because isPrime can handle every number between 3 and inputNum, but we can speed things up a little because of something we know about prime numbers. There are no even numbers that are prime, except for 2. This is why I tested 1 and 2 separately. We can now reduce the number of calls to isPrime by simply making the calling loop:
            For i = 3 To inputNum Step 2
                If isPrime(i) Then
                    primeNumbers &= "," & i
                End If
            Next


By adding a Step value of 2, we automatically test ONLY odd numbers.

In isPrime, the actual operation at the center of the loops will be:
     If testnum mod ctr = 0 then ...



I have something I need to do right now, but I'll get back to you within a few hours with more on the inner loop in isPrime. Let me know how you're doing, and if you have any questions.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2