Prime Numbers
Author Message
Prime Numbers

has anyone got some VB code to detect Prime Numbers in a For...Next
loop
I am using VB5

Sat, 11 Feb 2012 21:38:44 GMT
Prime Numbers

Quote:

> has anyone got some VB code to detect Prime Numbers in a For...Next
> loop
> I am using VB5

--
Jim Mack
Twisted tees at http://www.cafepress.com/2050inc
"We sew confusion"

Sat, 11 Feb 2012 22:30:01 GMT
Prime Numbers

Quote:
> has anyone got some VB code to detect Prime Numbers in a For...Next
> loop
> I am using VB5

I've had this sitting around for years:

-----BEGIN CODE
Private Function IsPrime(ByVal dblNumberToTest As Double) As Boolean

Dim dblDivisor As Double
Dim bResult As Boolean

'We can eliminate non-whole numbers immediately.
'Of course, we could specify the data type of the passed
'value to be a Long, but then we can only determine primes
'up to 2,147,483,647 whereas a double allows up to
'1.79769313486231E308 (see Data Type Summary in VB's Help).
'This also means that there is the potential of being able
'to pass a non-whole number, and that's not good, since,
'by definition, a prime number must be a whole number.
If Not IsWholeNumber(dblNumberToTest) Then
IsPrime = False
Exit Function
End If

'We can also immediately eliminate all even numbers
'greater than 2.  This will allow us to reduce the
'iterations in the loop below by half.
If dblNumberToTest = 2 Then
IsPrime = True
Exit Function
Else
If dblNumberToTest Mod 2 = 0 Then
IsPrime = False
Exit Function
End If
End If

'Now loop through all odd numbers up to the square root
'of the dividend.  This means the primes for any given range
'can be determined SIGNIFICANTLY faster.  Want to see this for
'yourself?  Uncomment the 2nd FOR statement below and comment
'the 1st one.  Both yield the exact same results but be prepared
'to wait a little longer using the 2nd FOR statement.

For dblDivisor = 3 To Int(Sqr(dblNumberToTest)) Step 2
'For dblDivisor = 3 To dblNumberToTest - 1 Step 2
bResult = (dblNumberToTest Mod dblDivisor = 0)
'As soon as a number divides evenly, we know it can't be
'prime, so return false and exit
If bResult = True Then
IsPrime = False
Exit Function
End If
Next

'If we get completely through the loop, we've found nothing
'that divides evenly into the number which we're testing.
IsPrime = True

End Function

Private Function IsWholeNumber(ByVal dblNum As Double) As Boolean

'There's probably a better way to do this using
'math functions, but I didn't feel like figuring
'it out.  :)

Dim sNumber As String

sNumber = CStr(dblNum)

If InStr(sNumber, ".") Then
IsWholeNumber = False
Else
IsWholeNumber = True
End If

End Function
-----END CODE

Now, just loop through the range of numbers you want to determine are prime
and call IsPrime for each one.

--
Mike

Sat, 11 Feb 2012 22:42:06 GMT
Prime Numbers

<cut>

Quote:
>    'Of course, we could specify the data type of the passed
>    'value to be a Long, but then we can only determine primes
>    'up to 2,147,483,647 whereas a double allows up to
>    '1.79769313486231E308 (see Data Type Summary in VB's Help).
<cut>
>        If dblNumberToTest Mod 2 = 0 Then

I think you will find those two snippets to be contradictory since the Mod
operator won't work unless the value can be coerced to a Long

Sat, 11 Feb 2012 23:04:00 GMT
Prime Numbers

Quote:

> <cut>
>>    'Of course, we could specify the data type of the passed
>>    'value to be a Long, but then we can only determine primes
>>    'up to 2,147,483,647 whereas a double allows up to
>>    '1.79769313486231E308 (see Data Type Summary in VB's Help).
> <cut>
>>        If dblNumberToTest Mod 2 = 0 Then

> I think you will find those two snippets to be contradictory since the Mod
> operator won't work unless the value can be coerced to a Long

The point is to determine if it's a whole number BEFORE entering into the
loop. Sure, it might not make a difference on today's PCs.  15+ years ago on
386 computers, it did.

--
Mike

Sun, 12 Feb 2012 02:27:30 GMT
Prime Numbers

Quote:

>> <cut>
>>>    'Of course, we could specify the data type of the passed
>>>    'value to be a Long, but then we can only determine primes
>>>    'up to 2,147,483,647 whereas a double allows up to
>>>    '1.79769313486231E308 (see Data Type Summary in VB's Help).
>> <cut>
>>>        If dblNumberToTest Mod 2 = 0 Then

>> I think you will find those two snippets to be contradictory since the
>> Mod operator won't work unless the value can be coerced to a Long

> The point is to determine if it's a whole number BEFORE entering into the
> loop. Sure, it might not make a difference on today's PCs.  15+ years ago
> on 386 computers, it did.

My point is that your test using Mod limits the procedure to values that fit
into a Long so allowing a Double and testing for a non-integer doesn't make
sense.  It you want to keep that then you need to change the test for
multiples of 2 so that it doesn't use Mod.

Sun, 12 Feb 2012 02:32:35 GMT
Prime Numbers

Quote:

> has anyone got some VB code to detect Prime Numbers in a For...Next
> loop
> I am using VB5

This is a bit messy and slow, but it should show you the way.

Dim testnumber As Long
Dim divisor As Long
Dim isprime As Boolean
Dim range As Long
Dim start As Long

start = Timer

range = 1000000

Debug.Print 2
Debug.Print 3
Debug.Print 5
Debug.Print 7

For testnumber = 9 To range Step 2

divisor = 2
isprime = True
Do While divisor * divisor <= testnumber
If testnumber Mod divisor = 0 Then
isprime = False
Exit Do
End If
divisor = divisor + 1
Loop

If isprime = True Then
Debug.Print testnumber
isprime = False
End If
Next testnumber
Debug.Print "total time = " + Str(Int(Timer - start)) + " seconds"

You can extend this by only using previous primes as divisors as well, this
would speed things up dramatically, however, you'd need to keep these in an
array or something. With bigger numbers you could run out of ram.

--
HK

Sun, 12 Feb 2012 02:50:45 GMT
Prime Numbers
...

Quote:
> My point is that your test using Mod limits the procedure to values that
> fit into a Long so allowing a Double and testing for a non-integer
> doesn't make sense.  It you want to keep that then you need to change
> the test for multiples of 2 so that it doesn't use Mod.

To make the problem more precise, since a Double has 53 bits of mantissa
and a Long is a (signed) 32, the results of 2^31 and greater overflow in
a VB Long whereas they are both exact in a Double

To make the comparison/test w/ a Double one would need to perform the
division explicitly in VB rather than relying on the Mod operation that
isn't valid for more precision than a Long can hold.

--

Sun, 12 Feb 2012 02:51:31 GMT
Prime Numbers

Quote:

>>> <cut>
>>>>    'Of course, we could specify the data type of the passed
>>>>    'value to be a Long, but then we can only determine primes
>>>>    'up to 2,147,483,647 whereas a double allows up to
>>>>    '1.79769313486231E308 (see Data Type Summary in VB's Help).
>>> <cut>
>>>>        If dblNumberToTest Mod 2 = 0 Then

>>> I think you will find those two snippets to be contradictory since the
>>> Mod operator won't work unless the value can be coerced to a Long

>> The point is to determine if it's a whole number BEFORE entering into the
>> loop. Sure, it might not make a difference on today's PCs.  15+ years ago
>> on 386 computers, it did.

> My point is that your test using Mod limits the procedure to values that
> fit into a Long so allowing a Double and testing for a non-integer doesn't
> make sense.  It you want to keep that then you need to change the test for
> multiples of 2 so that it doesn't use Mod.

Sorry.  I misunderstood.

Sun, 12 Feb 2012 02:54:41 GMT
Prime Numbers

Quote:

> ...
>> My point is that your test using Mod limits the procedure to values that
>> fit into a Long so allowing a Double and testing for a non-integer
>> doesn't make sense.  It you want to keep that then you need to change the
>> test for multiples of 2 so that it doesn't use Mod.

> To make the problem more precise, since a Double has 53 bits of mantissa
> and a Long is a (signed) 32, the results of 2^31 and greater overflow in a
> VB Long whereas they are both exact in a Double

> To make the comparison/test w/ a Double one would need to perform the
> division explicitly in VB rather than relying on the Mod operation that
> isn't valid for more precision than a Long can hold.

As I said, that was code I've had for years. The file date of the module is
4/27/1992. I don't even rmember if I wrote it or obtained it from
somewhere/someone.  <g>

--
Mike

Sun, 12 Feb 2012 03:38:59 GMT
Prime Numbers
...

Quote:
> As I said, that was code I've had for years. The file date of the module
> is 4/27/1992. I don't even rmember if I wrote it or obtained it from
> somewhere/someone.  <g>

Longs and Doubles had the same restrictions then as well... :)

--

Sun, 12 Feb 2012 05:34:03 GMT
Prime Numbers

Quote:

> You can extend this by only using previous primes as divisors as well, this
> would speed things up dramatically, however, you'd need to keep these in an
> array or something. With bigger numbers you could run out of ram.

This uses an array to store the primes into in order to use only primes as
divisors. This speeds things up a bit, but the ReDim Preserve is kinda
expensive time wise. A linked list would be faster, but no can do in VB.
This was done in VB6 but it should also work kin VB5

Dim testnumber As Long
Dim divisor As Long
Dim isprime As Boolean
Dim range As Long
Dim start As Long
Dim primearray() As Long
Dim newsize As Long
Dim arrayindex As Long

start = Timer
'highest number to test

range = 1000000
'get these out of the way right off
Debug.Print 2
Debug.Print 3
Debug.Print 5
Debug.Print 7

'put these first primes in the array
ReDim Preserve primearray(3)
primearray(0) = 2
primearray(1) = 3
primearray(2) = 5
primearray(3) = 7

'test only odd numbers
For testnumber = 9 To range Step 2
'set first divisor to the first prime = 2
arrayindex = 0
divisor = primearray(arrayindex)
isprime = True
'check only to the sqare root of the testnumber (divisor * divisor) is
way faster
' than sqr(testnumber)
Do While divisor * divisor <= testnumber
If testnumber Mod divisor = 0 Then
isprime = False
Exit Do
End If
'index the array by one
arrayindex = arrayindex + 1
'get next prime to use as divisor
divisor = primearray(arrayindex)
Loop

If isprime = True Then
'show the prime value
Debug.Print testnumber
'increase array size by 1 and store next prime in new array index
newsize = UBound(primearray, 1) + 1
ReDim Preserve primearray(newsize)
primearray(newsize) = testnumber
End If
Next testnumber
'display elapsed time
Debug.Print "total time = " + Str(Int(Timer - start)) + " seconds"
--
HK

Sun, 12 Feb 2012 07:11:50 GMT
Prime Numbers

Quote:

> ...
>> As I said, that was code I've had for years. The file date of the module
>> is 4/27/1992. I don't even rmember if I wrote it or obtained it from
>> somewhere/someone.  <g>

> Longs and Doubles had the same restrictions then as well... :)

Yes, but I was a newbie then.  <g>

--
Mike

Sun, 12 Feb 2012 08:15:49 GMT
Prime Numbers

Quote:

>> ...
>>> As I said, that was code I've had for years. The file date of the
>>> module is 4/27/1992. I don't even rmember if I wrote it or obtained
>>> it from somewhere/someone.  <g>

>> Longs and Doubles had the same restrictions then as well... :)

> Yes, but I was a newbie then.  <g>

Ahhh...bringing out the heavy defensive weaponry now, huh???  <VBG>

--

Sun, 12 Feb 2012 08:25:47 GMT
Prime Numbers

Quote:

>>> ...
>>>> As I said, that was code I've had for years. The file date of the
>>>> module is 4/27/1992. I don't even rmember if I wrote it or obtained it
>>>> from somewhere/someone.  <g>

>>> Longs and Doubles had the same restrictions then as well... :)

>> Yes, but I was a newbie then.  <g>

> Ahhh...bringing out the heavy defensive weaponry now, huh???  <VBG>

Sheesh, you guys can be brutal.  Here I thought I'd just help the OP out by
posting some very old code I had sitting around. Didn't know it'd turn into
this.  I guess people are desperate to post messages to keep this newgroup
alive.  <g>

--
Mike

Sun, 12 Feb 2012 08:43:34 GMT

 Page 1 of 2 [ 25 post ] Go to page: [1] [2]

Relevant Pages