Author |
Message |
messianic ligh #1 / 25
|
 Prime Numbers
has anyone got some VB code to detect Prime Numbers in a For...Next loop I am using VB5 Thanks In Advance
|
Sat, 11 Feb 2012 21:38:44 GMT |
|
 |
Jim Mac #2 / 25
|
 Prime Numbers
Quote:
> has anyone got some VB code to detect Prime Numbers in a For...Next > loop > I am using VB5 > Thanks In Advance
Google "vb -net eratosthenes" -- Jim Mack Twisted tees at http://www.cafepress.com/2050inc "We sew confusion"
|
Sat, 11 Feb 2012 22:30:01 GMT |
|
 |
Mike #3 / 25
|
 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 |
|
 |
Bob Butle #4 / 25
|
 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 |
|
 |
Mike #5 / 25
|
 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 |
|
 |
Bob Butle #6 / 25
|
 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 |
|
 |
H-Ma #7 / 25
|
 Prime Numbers
Quote:
> has anyone got some VB code to detect Prime Numbers in a For...Next > loop > I am using VB5 > Thanks In Advance
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 |
|
 |
dpb #8 / 25
|
 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 |
|
 |
Mike #9 / 25
|
 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 |
|
 |
Mike #10 / 25
|
 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 |
|
 |
dpb #11 / 25
|
 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 |
|
 |
H-Ma #12 / 25
|
 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 |
|
 |
Mike #13 / 25
|
 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 |
|
 |
dpb #14 / 25
|
 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 |
|
 |
Mike #15 / 25
|
 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 |
|
|