Prime Numbers - Using a Function

dawnb1
05-31-2005, 02:35 PM
I'm a newbie to VB and I have an assignment as follows.. User enters a low bound (number) and then a high bound - and a Function called Prime must return true or false, and then display all prime numbers between the two bounds in a textbox. Example between 2 and 20 - the following must be displayed in the textbox 2, 3, 5, 7, 11, 13, 17, 19.....

I just learned about Functions, but I have NO idea how to make VB determine prime... any idea's?

Please help...

jpaugh78
05-31-2005, 02:38 PM
i found this using google:
http://www.xtremecomp.com/tips/xttip19.htm

Bolek
05-31-2005, 03:02 PM
As far as I know the only way to determine if a number is prime is to try it. You can try it by the definition of prime which says that a prime is such a number that can only be divided by 1 and itself. So to determine if a number is a prime, you try to divide it by all numbers from 2 to sqrt(that_number)+1. If it cannot be divided by any of these number, it is a prime. If it can be divided, it is not a prime. To find if it can divided, use a mod b which gives the remainder of a divided by b.

Obviusly, all numbers are divisible by 1. You can save some time by dividing just by 2 and leave out any even numbers greater than two because if a number is not divisible by 2, then it is not divisible by any of its multiples.

To the sqrt( ): it saves you much time and the reason behind is that if a number X can be divided by A, then it can also be divided by B=X/A. For example, the number 105=3*5*7 can be divided by 3, 5, 7, 15, 21 and 35. However, it is quite useless to try any number Y > sqrt(105) because surely 105/Y < sqrt(105). So only divisors D from 2 to sqrt(105) are of interest since all other divisors can be written as X/D.

So the code will be something like

public function IsPrime( byval X as long) as boolean
dim q as long, e as long
dim b as boolean

' Test two a special case
if x mod 2 = 0 then
isprime=false
exit function
endif

' Test odd numbers
b = true
e = sqrt(X)
q = 3
while b and (q<e)
if x mod q = 0 then b = false
q = q + 2
wend
IsPrime = b
end function


To the question of determining all prime numbers within a range. If the range is small enough than you can perhaps test all odd numbers in it with the above test. If the range is large, however, this will be very slow.

There's an algorithm called Eratosthenes's sieve, known from the times of the Ancient Greeks, which can find primes from 1 to any selected number and is much faster than testing each number.

The idea is as follows: make an array of numbers from 1 to N where N is the maximum number you are interested in. Fill each member with true. Now start with 2 and assign false to all members at index j=2+2*i, i>=1. This way, you assign false to all multiples of 2 - these surely are not primes. Repeat the thing with 3, assigning false to all members at index j=3+3*i, i>=1. This assign false to all multiples of 3. Skip 4 because it is already false so it and all its multiples are definitely not primes. For 5, assign false to all members at j=5*5+i, i>=1. Skip 6, 8, 9, 10, 12, 14, 15, 16, 18, 20 etc. since they are all false already. You do this with all numbers from 1 to sqrt(N)+1. At the end, primes will have true and non-primes false. This is a reasonably fast algorithm, much faster than testing each number with divisions.

dawnb1
05-31-2005, 03:06 PM
Thanks - I'll try these and see what I come up with...

OnErr0r
05-31-2005, 03:28 PM
Here's a little visual I did on the Sieve algo that Bolek described:

http://www.syix.com/wpsjr1/primes.html

Cerian Knight
05-31-2005, 07:48 PM
Here's a little visual I did on the Sieve algo that Bolek described:

http://www.syix.com/wpsjr1/primes.html

I have been curious how much things have changed with faster processors and noticed that your assembly version is actually a little slower than the VB on my Pentium M at both 600 and 1600 MHz. This parallels the performance of an asm DLL I wrote to (try to) improve speed in one of my VB projects, as well.

Just goes to prove the power of VB with advanced optimizations enabled coupled with speculative execution, etc.

Asm is truly dead, unless you REALLY need the space, use MMX, SSE, etc, or just want to truly understand how computers work. :(

Sorry about going on a tangent here.

OnErr0r
05-31-2005, 09:25 PM
I also get very similar times on my P3 1.1 GHZ. However, that's an apples and oranges comparison. :)

The ASM version is calculating the primes via the sieve AND writing them out in ASCII (open it in Wordpad, not Notepad). The VB version opens a memory mapped file and dumps four byte longs, no ascii conversion. Try sieve() instead of sieve3(), it takes more than twice as long here.

Not as big of a difference as on my P233MMX, but I didn't optimize it for a P3 either. ;)

I've got a C++ version I wrote more recently that does up to 1M in ~10ms. That's just the sieve portion.

Bolek
06-01-2005, 12:36 AM
I have been curious how much things have changed with faster processors and noticed that your assembly version is actually a little slower than the VB on my Pentium M at both 600 and 1600 MHz. This parallels the performance of an asm DLL I wrote to (try to) improve speed in one of my VB projects, as well.

Did you write your ASM DLL with correct instruction scheduling, pipelining and all that optimizations in mind? Personally, I was too lazy to learn these things so I do not expect my ASM code be faster than the output of a well-optimizing compiler. However, I believe I could write a code at least as fast as that of the compiler if I learned all these things.

Second, ASM is still useful if you need some special instructions and these do not need to be too special. The obvious examples are CPUID, IN, OUT for cpu idenitification and output and input to/from hardware ports. You can use libraries but these libraries were written using inline ASM.

Another such instruction is the FSINCOS one. It should be twice as fast as SIN and COS called separately even on P4. If you need to compute 6 billions complex exponentials like me, that matters.

And the last but most important thing is that a better algorithm is always the best optimization. I have been working os some genetic computing recently that turned to computing one million Fourier transforms inside the fitness functions. I used the FFTW library (www.fftw.org), possibly the fastest FFT library I could find. The algorithm took 65 minutes to run in a 386-compatible mode. After recompiling FFTW with SSE, SSE2, MMX etc. on, it took 60 minutes. However, realizing the simple thing that (n mod 64) and (n and &h3F) gives the same result and rewriting an inlined indexing function accordingly saved me 20 minutes because that function was called about 10 billion times throughout the algorithm.

EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum