# Using A Loop/Array To Find Prime Numbers

• (2 Pages)
• 1
• 2

## 22 Replies - 47393 Views - Last Post: 05 April 2016 - 02:34 PMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=294813&amp;s=2eb4c7cfa7428ecb26faaaf4e017e701&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #16 CodyMcCoderson

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

## Re: Using A Loop/Array To Find Prime Numbers

Posted 09 October 2012 - 04:27 PM

Ok, So I made a couple changes, I dont know if they're correct, but thats why im trying.
But why does inputNum under Private Function not work, even though its dim under the module and not the sub?

Maybe I dont have this correct, but i've also been steadily working on 4 other questions for programming at the same time and this is the only one giving me a world of trouble and its getting to me. haha

You're help is greatly appreciated though and hopefully i'll get this soon. haha

```Module Module1
Dim inputNum As String = 0
Sub Main()

Do While inputNum <> "end"
Console.WriteLine(vbNewLine & "Please enter a number: ( 'end' to stop)")
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
For i = 3 To inputNum Step 2
If isPrime(i) Then
End If
Next

Console.WriteLine(vbNewLine & "Prime numbers up to " & inputNum)
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 inputNum = 3 To testnum
If testnum Mod ctr = 0 Then
isPrime = False
End If
Next
End Function

End Module

```

### #17 lar3ry

• Coding Geezer

Reputation: 313
• Posts: 1,296
• Joined: 12-September 12

## Re: Using A Loop/Array To Find Prime Numbers

Posted 09 October 2012 - 05:45 PM

CodyMcCoderson, on 09 October 2012 - 04:27 PM, said:

Ok, So I made a couple changes, I dont know if they're correct, but thats why im trying.
But why does inputNum under Private Function not work, even though its dim under the module and not the sub?

We cannot use inputNum as a counting variable in a For loop because it is a String. See further down for comments about the For loop in isPrime().

Fortunately, we don't require inputNum within the isPrime function. Why? Because in this function, we don't care about inputNum. The only number we care about is the one we pass to it, which is a test number. What we are doing is passing all the odd numbers from 3 to the value of imputNum, one at a time, and asking if it is prime or not. In the function declaration, after the ')', it says 'As Boolean', which means that the function MUST return a True or a False.

Quote

Maybe I dont have this correct, but i've also been steadily working on 4 other questions for programming at the same time and this is the only one giving me a world of trouble and its getting to me. haha

You're help is greatly appreciated though and hopefully i'll get this soon. haha

We'll be there soon. I promise.

Quote

```    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 inputNum = 3 To testnum
If testnum Mod ctr = 0 Then
isPrime = False
End If
Next
End Function

```

The inner For loop here is saying:
assign a value of 3 to inputNum
each time through the loop, increment inputNum by +1
leave the loop when we reach the value in testNum.

As you can see, asking a string to be a numeric counter is not going to work.

So, here we have testNum, passed into the isPrime() function. Notice we have set a variable called isPrime to True. There are (at least) two ways to return a value from a function. The first is to explicitly say "Return <value>", where <value must be either a variable of the proper type, or a value of that type. Up further where we say 'Return True', is an example of this method.

The other way is to assign a value to the name of the function, so 'isPrime = True' will retrun True to the caller without having to explicitly telling it what to return. It will return that value by saying 'Return', or by just 'falling out the bottom' of the function. The reason we set isPrime to True is because it is easier to prove a number non-prime than to prove it prime.

Except for the use of inputNum you came pretty close on the inner loop! Good job!

Try this:
```        For ctr = 3 To testnum \ 2 Step 2
If testnum Mod ctr = 0 Then
isPrime = False
Exit For
End If
Next

```

There are two things extra in there, but both are merely optimizations for speed and to avoid unnecessary operations.
we count ctr from 3 to 'testnum \ 2' because a number cannot be evenly divisible by a number more than half of it. What thes loop says is:
assign 3 to ctr
each time through, increment by +2 (to divide by only odd numbers)
leave the loop when we reach the integer value of testnum divided by 2

The 'Exit For' is there because once we find a number that divides evenly into testnum, there is no sense trying any further, because the number is already proven to be non-prime. An example. testnum = 99, and the first test is '99 mod 3', which will result in 0, so we only had to do one test on that number, instead of 25 tests or so.

When we 'fall out the bottom' of the function, it will return a True if the number is prime, or a False if the number is non-prime.

And there you go, a working program.
Study it in detail, perhaps using a breakpoint and stepping through one line at a time. If you understand what all is happening in there, it will go a long way toward making your next program easier.

Edited for spelling.

This post has been edited by lar3ry: 09 October 2012 - 07:55 PM

### #18 CodyMcCoderson

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

## Re: Using A Loop/Array To Find Prime Numbers

Posted 10 October 2012 - 10:04 AM

By reading what you just wrote, I understand what the hell is going on now 100% more then when my instructor explained it. He's so vague and simplistic. Now that you gave each word a meaning it really helped.

Thank you very, very much!

### #19 PeterH

• D.I.C Regular

Reputation: 49
• Posts: 256
• Joined: 03-September 09

## Re: Using A Loop/Array To Find Prime Numbers

Posted 10 October 2012 - 02:06 PM

For what its worth, I thought the manner in which lar3ry provided such excellent assistance during this post is to be highly praised. Patience, great explanations and an understanding of how to teach learners, without some of the patronising, dismissive or plain arrogant replies sometimes forthcoming.

Nice one lar3ry

### #20 CodyMcCoderson

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

## Re: Using A Loop/Array To Find Prime Numbers

Posted 10 October 2012 - 02:21 PM

He did it exactly how people trying to help should.

He explained, rather then just giving me the code.

Now I understand what im doing.

### #21 didanche

Reputation: -1
• Posts: 1
• Joined: 05-April 16

## Re: Using A Loop/Array To Find Prime Numbers

Posted 05 April 2016 - 10:30 AM

```Private Sub primeButton_Click(sender As Object, e As EventArgs) Handles primeButton.Click
'Clear the results box if a new button is being pressed
resultListBox.Items.Clear()

'Check if either of the textboxes are empty
If firstTextBox.Text = String.Empty OrElse secondTextBox.Text = String.Empty Then
MessageBox.Show("Missing data error: please input a number in each box.", "Data Missing", MessageBoxButtons.OK, MessageBoxIcon.Error, MessageBoxDefaultButton.Button1)
firstTextBox.Focus()

Else
Integer.TryParse(firstTextBox.Text, first)
Integer.TryParse(secondTextBox.Text, second)

'Check if the first number is less than the second
If first > second Then
MessageBox.Show("The first number should be smaller than the second.", "Input Error", MessageBoxButtons.OK, MessageBoxIcon.Error, MessageBoxDefaultButton.Button1)
firstTextBox.Focus()
firstTextBox.SelectAll()

Else
'Check if the second is less than 500
If second > 500 Then
MessageBox.Show("The second number should not be greater than 500 for this operation.", "Input Error", MessageBoxButtons.OK, MessageBoxIcon.Exclamation, MessageBoxDefaultButton.Button1)
secondTextBox.Focus()
secondTextBox.SelectAll()

Else
'Make a counter
Dim counter As Integer

'Create a variable that will hold each number to test for prime within the first and second number specified by the user
For i As Integer = first To second

'Create a variable that will test the number above for if it is prime
For n As Integer = 1 To i

'Count with the counter how many times the number will divide and get an integer answer
If i Mod n = 0 Then

'If the answer is integer, aka the MOD calc comes out to 0, increment the counter
counter += 1

End If

Next

'A prime number will only be able to divide into 1 and itself, and no other numbers
'Therefore, a true prime number will tick a counter of 2
'Any other number will have a counter of greater than 2

If counter = 1 OrElse counter = 2 Then

'If the counter is 2, then the number is prime, so display that number into the result box

End If

'Reset the counter to test the next number in the series between the specified first and second number
counter = 0

Next

End If
End If
End If

```

This post has been edited by macosxnerd101: 05 April 2016 - 02:32 PM
Reason for edit:: If you're going to necro a post, please at least use code tags

### #22 dday9

• D.I.C Regular

Reputation: 60
• Posts: 317
• Joined: 17-April 13

## Re: Using A Loop/Array To Find Prime Numbers

Posted 05 April 2016 - 01:13 PM

I will admit that I did not take the time to read all of the post in this thread, so keep that in mind when you read this.

I never understood why people are so fascinated by prime numbers or why programming classes want students to calculate them; to me prime number counting pointless. I did, however want to do this exercise since I've never done a prime number function before and I wanted to make the code as short as possible. So I came up with this function:

```Private Function FindPrime(ByVal uBounds As UInteger) As Integer()
If uBounds < 2 Then
Throw New ArgumentOutOfRangeException("The uBounds parameter must be a valid number greater than 2.")
End If

Return(From number As Integer In Enumerable.Range(2, CInt(uBounds) - 1) Where Enumerable.Range(2, number).Count(Function(p) number mod p = 0) = 1).ToArray()
End Function
```

Fiddle: https://dotnetfiddle.net/Ltt8EZ

Explanation:
• I create a funciton that accepts a single parameter
• I first check if the argument passed is less than 2 and if it is then I throw an exception since a prime number must be a natrual number greater than 1.
• I then return an Array where the values 2 - uBounds(-1 for 0 based index) can only be divisible by itself.

Edit: Lol, this thread is 3 and a half years old. My bad y'all for posting after a resurrecter.

This post has been edited by dday9: 05 April 2016 - 01:32 PM

### #23 macosxnerd101

• Games, Graphs, and Auctions

Reputation: 11796
• Posts: 44,320
• Joined: 27-December 08

## Re: Using A Loop/Array To Find Prime Numbers

Posted 05 April 2016 - 02:34 PM

Quote

to me prime number counting pointless.

Prime numbers are very important in cryptography. The RSA algorithm, which is used for securing your online purchases, is based on the fact that factoring integers is a hard problem. Interestingly enough though, factoring integers is not known to be NP-Hard and is believed to be NP-Intermediate (that is, if P != NP, then INTEGER FACTORIZATION is believed to be in NP but neither in P nor NP-Complete).