Qbasicnews.com

QbasicNews.Com => Challenges => Topic started by: Touf on May 04, 2003, 09:46:41 PM



Title: The PRIME NUMBERS
Post by: Touf on May 04, 2003, 09:46:41 PM
Come and participate to this new challenge !
http://ToufQb.free.fr/Concours.php?langue=1

Well , let's see if you know your division and multiplication charts .... :D

This is a NO TIME LIMIT contest !


Title: The PRIME NUMBERS
Post by: toonski84 on May 04, 2003, 10:03:48 PM
this works well enough for me.

Code:
INPUT number&

FOR y& = 1 TO number&
  prime% = 0
  FOR x& = 2 TO SQR(y&) - 1
    IF y& / x& = y& \ x& THEN prime% = 1
  NEXT x&
  IF prime% = 0 THEN PRINT y&
NEXT y&


Title: The PRIME NUMBERS
Post by: Plasma on May 04, 2003, 10:09:48 PM
I emailed mine...


Title: The PRIME NUMBERS
Post by: Touf on May 05, 2003, 09:54:21 AM
Please , send your programs by e-mail , then I'll be able to upload my website .
Thanx


Title: The PRIME NUMBERS
Post by: Touf on May 07, 2003, 12:23:12 AM
Nobody else to compete ?

Anyway , congratulations to Plasma357 for its very very fast program !

I couldn't believe it !

It's gonna be hard to do better !


Title: The PRIME NUMBERS
Post by: Mango on May 07, 2003, 03:51:28 PM
Quote from: "Touf"
Nobody else to compete ?

Anyway , congratulations to Plasma357 for its very very fast program !

I couldn't believe it !

It's gonna be hard to do better !


This is what I usually use...it stores the small primes in an array then doesn't bother testing the suspect prime against nonprime factors.   By changing lines that were commented out, you can make the program print every prime, output the primes to the file primes.dat, or  print the most recent prime 1 time/sec.  

Code:
DEFINT A-Z
DIM smallprimes(1 TO 5000) AS INTEGER
CLS
a = 0
max = 3
maxsqur = max * max
smallprimes(1) = 3
next1 = 5
count = 1
'OPEN "primes.dat" FOR BINARY AS 1
'vvvvvvvvvvvvvvvvvvvvvvvvvvvv'get little primes (first 3500) and put into an array---------------
DO WHILE count < 3500      
 DO
  a = a + 1
  IF next1 MOD smallprimes(a) = 0 THEN GOTO notprime
 LOOP WHILE smallprimes(a) * smallprimes(a) < next1

 count = count + 1
 smallprimes(count) = next1
 PRINT smallprimes(count);        'found a prime
 'PUT 1, , next1

notprime:
next1 = next1 + 2
a = 0
LOOP
'^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
nextbig& = next1 - 2
CLS
over:
t& = TIMER
'vvvvvvvvvvvvvvvvvvvvvvvvvvvvv'get big primes
DO        
 DO
   a = a + 1
   IF nextbig& MOD smallprimes(a) = 0 THEN GOTO notprime2
 LOOP WHILE (nextbig& \ smallprimes(a)) > smallprimes(a)

  recent& = nextbig&   'found a prime
 'PRINT nextbig&;
 'PUT 1, , nextbig&

notprime2:
nextbig& = nextbig& + 2
a = 0
LOOP UNTIL TIMER - t& > 1
'^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
LOCATE 1
PRINT recent&
GOTO over


I thought this was a pretty fast way of getting them until I saw the program:

Code:
'Prime Number Generator
'Algorithm from Knuth's "Sorting and Searching" Page 617
'Programmed by Rich Geldreich
'
'Notes:  This  prime   number   generator   uses   a   disk   file
'"PRIMEBUF.BIN" to hold the prime numbers, so little RAM memory is
'needed.   Each  prime  number  is  represented  as the difference
'between the last prime number by  a single byte.  In other words,
'the gap between each prime number is stored instead of each prime
'number itself.  All gaps are even  numbers,  because  all  primes
'must be odd numbers.  Therefore, each byte can represent a gap of
'up  to  510, because the least significant bit of each gap length
'is always unused.  (Except for the special cases of 1-2, and 2-3.
'These primes aren't stored in  the  disk file; they're assumed to
'be present.) Since the maximum gap between all consecutive primes
'up to 436,273,009 is only 286, a single byte is good  enough  for
'this program!)
'
'The  program  stops  when  escape is pressed or when the priority
'queue is full.
'
'On a 286/10, roughly 3.2 million prime numbers were calculated in
'about 2.5 hours by this program.
'
DEFINT A-Z

DECLARE SUB PutPrime (a&)
DECLARE FUNCTION GetPrime& ()

'Maximum prime candidate = HeapSize*HeapSize
CONST HeapSize = 4096
CONST IOSize = 2048

OPEN "primebuf.bin" FOR OUTPUT AS #1: CLOSE #1
OPEN "primebuf.bin" FOR BINARY AS #1

DIM SHARED PrimeBuf1 AS STRING * IOSize, Buf1Loc, Buf1FLoc AS LONG
DIM SHARED PrimeBuf2 AS STRING * IOSize, Buf2Loc, Buf2FLoc AS LONG
DIM SHARED SlideFlag
DIM SHARED LastPrime1&, LastPrime2&

Buf1Loc = 1 + (1 - 1): Buf1FLoc = 1
Buf2Loc = 1 + (2 - 1): Buf2FLoc = 1
LastPrime1& = 3
LastPrime2& = 5

'Priority queue
DIM HeapQ(1 TO HeapSize) AS LONG
DIM HeapQ1(1 TO HeapSize) AS LONG
DIM HeapQ2(1 TO HeapSize) AS LONG

DIM SHARED n AS LONG
DIM t AS LONG
DIM Q AS LONG, Q1 AS LONG, Q2 AS LONG
DIM TQ AS LONG, TQ1 AS LONG
DIM u AS LONG

n = 5
d = 2
r = 1
t = 25
HeapQ(1) = 25
HeapQ1(1) = 10
HeapQ2(1) = 30

DO
  DO
    Q = HeapQ(1)
    Q1 = HeapQ1(1)
    Q2 = HeapQ2(1)

    TQ = Q + Q1
    TQ1 = Q2 - Q1

    '***Insert Heap(1) into priority queue
    i = 1
    DO
        j = i * 2
        IF j <= r THEN
            IF j < r THEN
                IF HeapQ(j) > HeapQ(j + 1) THEN
                  j = j + 1
                END IF
            END IF

            IF TQ > HeapQ(j) THEN
                HeapQ(i) = HeapQ(j)
                HeapQ1(i) = HeapQ1(j)
                HeapQ2(i) = HeapQ2(j)
                i = j
            ELSE
                EXIT DO
            END IF
        ELSE
            EXIT DO
        END IF
    LOOP
    HeapQ(i) = TQ
    HeapQ1(i) = TQ1
    HeapQ2(i) = Q2
    '***

  LOOP UNTIL n <= Q

  DO WHILE n < Q
    PutPrime n
    n = n + d
    d = 6 - d
  LOOP

  IF n = t THEN

    u = GetPrime
    t = u * u

    '***Find location for new entry
    j = r + 1
    DO
      i = j \ 2
      IF i = 0 THEN
        EXIT DO
      END IF
      IF HeapQ(i) <= t THEN
        EXIT DO
      END IF
      HeapQ(j) = HeapQ(i)
      HeapQ1(j) = HeapQ1(i)
      HeapQ2(j) = HeapQ2(i)
      j = i
    LOOP
    '***
    HeapQ(j) = t
    IF (u MOD 3) = 2 THEN
      HeapQ1(j) = 2 * u
    ELSE
      HeapQ1(j) = 4 * u
    END IF
    HeapQ2(j) = 6 * u

    r = r + 1
    IF r = HeapSize THEN 'Don't overflow priority queue
      EXIT DO
    END IF

  END IF

  n = n + d
  d = 6 - d

LOOP UNTIL LEN(INKEY$)

'Print prime numbers calculated. (Except for the last few
'which are still in the output buffer.)

CLS
SEEK #1, 1
LastPrime& = 3
PRINT 1; 2; 3;
FOR a = 1 TO LOF(1) \ IOSize
  GET #1, , PrimeBuf1
  FOR b = 1 TO IOSize
    LastPrime& = LastPrime& + ASC(MID$(PrimeBuf1, b, 1)) * 2
    PRINT LastPrime&;
  NEXT
  IF LEN(INKEY$) THEN EXIT FOR
NEXT
CLOSE
END

FUNCTION GetPrime&

  IF SlideFlag = 0 THEN
    LastPrime2& = LastPrime2& + 2 * ASC(MID$(PrimeBuf1, Buf2Loc, 1))
  ELSE
    LastPrime2& = LastPrime2& + 2 * ASC(MID$(PrimeBuf2, Buf2Loc, 1))
  END IF
  GetPrime& = LastPrime2&

  Buf2Loc = Buf2Loc + 1
  IF Buf2Loc = (IOSize + 1) THEN
    Buf2FLoc = Buf2FLoc + IOSize
    GET #1, Buf2FLoc, PrimeBuf2
    Buf2Loc = 1
  END IF

END FUNCTION

SUB PutPrime (a&)

  STATIC TotalPrimes AS LONG

  MID$(PrimeBuf1, Buf1Loc) = CHR$((a& - LastPrime1&) \ 2)
  Buf1Loc = Buf1Loc + 1

  IF Buf1Loc = (IOSize + 1) THEN
    TotalPrimes = TotalPrimes + IOSize
    LOCATE , 1
    PRINT "Primes found:"; TotalPrimes; "Maximum candidate:"; n;

    PUT #1, Buf1FLoc, PrimeBuf1
    Buf1Loc = 1
    Buf1FLoc = Buf1FLoc + IOSize

    IF SlideFlag = 0 THEN
      SlideFlag = -1
      PrimeBuf2 = PrimeBuf1
    END IF
  END IF

  LastPrime1& = a&

END SUB


Now this one is what I call fast!!!


Title: The PRIME NUMBERS
Post by: ak00ma on May 07, 2003, 05:25:38 PM
Code:

DIM prime%(32000)
FOR n% = 3 TO SQR(32000) STEP 2
 FOR nn%= i * i TO 32000 STEP 2 * i
  prime%(nn%) = 1
 NEXT nn%
NEXT n%
FOR n% = 3 TO 32000 STEP 2
 IF prime%(n%) = 0 THEN PRINT n%
NEXT n%


Title: The PRIME NUMBERS
Post by: RST on May 07, 2003, 05:34:21 PM
Just a quick question....

Does the program have to find *all* primes, or *just* primes? Obviously, programs will go a lot faster if it's just the second one.


Title: The PRIME NUMBERS
Post by: DrV on May 07, 2003, 09:52:26 PM
Hehe... obvious answer is "no" because there are theroretically infinite number of prime numbers...  unless you mean within the range of a long int or something.


Title: The PRIME NUMBERS
Post by: Agamemnus on May 08, 2003, 12:04:50 AM
Yeah... there is an infinite number of primes.

But is there an infinite number of double primes (3 5, 11 13, 17 19, 101 103)?


Title: The PRIME NUMBERS
Post by: RST on May 08, 2003, 11:12:37 AM
A word of clarrification....  

I meant is it OK if the program skips a prime? For example, there's a few well-known algorithms that generate prime numbers, but they skip most of them. (eg: 3, 5, 11, 13.... [Skips 7])

I should point out that these algorthims are considerably faster than others.


Title: The PRIME NUMBERS
Post by: Touf on May 08, 2003, 02:22:39 PM
Am i dreaming ???

Of course ALL prime numbers have to be found !
If any prime number is forgotten , the program won't be accepted !

But please , mail me your programs , don't show it ...


Title: The PRIME NUMBERS
Post by: Touf on May 12, 2003, 09:47:25 AM
Short message for Mango ....

Can you please send me your e-mail and some informations about you ( see http://ToufQb.free.fr/classement.php?langue=1 )

Of course , if you don't want , don't do it  :wink:


Title: The PRIME NUMBERS
Post by: Mango on May 12, 2003, 11:53:48 AM
Quote from: "Touf"
Short message for Mango ....


Touf,  I'll be glad to send info...however, I wanted to make sure you were giving credit where it is due.  The 1st program I listed is my own method...the second was conceptualized and programmed by someone else...

It is unclear from your web-site which program was used.

Also...to be fair to all the methods, they should be compiled, because interpreted qbasic slows down when comments are present, and for spaces between lines of code!!!

Cheers


Title: The PRIME NUMBERS
Post by: Touf on May 12, 2003, 06:52:11 PM
lol
I've understood that your program was the first or the two ones !
But the program I'v tested is YOURS ...

The other-one is REALLY the BEST , but I don't manage to make it stop at a specified number ... doesn't matter ... I've no info on this programmer .

So , I won't class the second program .

 :wink:


Title: The PRIME NUMBERS
Post by: wizardlife on May 12, 2003, 07:11:35 PM
Quote from: "RST"
A word of clarrification....  

I meant is it OK if the program skips a prime? For example, there's a few well-known algorithms that generate prime numbers, but they skip most of them. (eg: 3, 5, 11, 13.... [Skips 7])

I should point out that these algorthims are considerably faster than others.


Those break down after a point though... I read uh... some article on it once... yeah...

Are there actually algos that consistently and accurately generate primes?


Title: The PRIME NUMBERS
Post by: Antoni Gual on May 13, 2003, 06:31:57 PM
It seems the only way to find all primes is to use the old Erathostenes's sieve. Even the second progam Mango posts is using it in a very convoluted way. The complication is to keep the primes stored in a file and only a sliding window on the sieve. The only goal of all this is to save memory, the sieve is still at the base.

This Rich Geldreich's code has been in the ABC packets since it's creation in 1995, but it mentions a 486 in the comments so I imagine the program has more  than 10 years!
I have tested it, it calculates all primes up to 2 000 000 in 6 seconds, then it needs 50 seconds to display them..


Title: The PRIME NUMBERS
Post by: Touf on May 28, 2003, 09:46:05 PM
So , Mango ?
Can I have some informations about you ? ... because NOBODY has reach your level for the moment !

( City , mail , URL ( if u have one ) ) .. you can send me these informations by mail if you want .


Title: The PRIME NUMBERS
Post by: Mango on May 29, 2003, 02:16:43 PM
Quote from: "Touf"
NOBODY has reach your level for the moment !/quote]

I just looked at the code I wrote earlier...and tweaked it a bit.  This one is about 75% faster.  The difference is I moved a squareroot out of a loop, and I got rid of a comparison and a goto.

Code:
DEFINT A-Z           'Joe Campbell-2003
DIM smallprimes(1 TO 3500) AS INTEGER  'array holds forst 3500 prime numbers
CLS
PRINT "This program finds primes, then prints the highest found, 1 per second"
a = 0        
max = 3
smallprimes(1) = 3
next1 = 5
count = 1
DO WHILE count < 3500
sqroot = SQR(next1)
DO
  a = a + 1
  IF next1 MOD smallprimes(a) = 0 THEN GOTO notprime
LOOP WHILE sqroot > smallprimes(a)
count = count + 1
smallprimes(count) = next1
notprime:
next1 = next1 + 2
a = 0
LOOP
nextbig& = next1 - 2
over:  
t& = TIMER
t1& = t& + 1
DO
sqroot = SQR(nextbig&)
DO
 a = a + 1
 IF sqroot < smallprimes(a) THEN  
    APrime& = nextbig&
    EXIT DO
 END IF
LOOP WHILE nextbig& MOD smallprimes(a)  
nextbig& = nextbig& + 2
a = 0  
LOOP UNTIL TIMER > t1&
LOCATE 2
PRINT APrime&
GOTO over


Title: The PRIME NUMBERS
Post by: Touf on June 02, 2003, 08:31:41 AM
haha !
A french programer has send a faster program !

Are the French programers better than US programers ?? :???:

lol


Title: And the Russians beat the French.
Post by: Agamemnus on June 02, 2003, 03:34:21 PM
Code:

CLS
DIM prime(1 TO 5000) AS INTEGER, cur.prime.amount AS INTEGER
cur.prime.amount% = 1
prime%(1) = 2
i% = 3
1 j% = 0
sqrt.num% = SQR(i%)
2 j% = j% + 1
temp% = prime%(j%)
IF i% MOD temp% = 0 THEN GOTO 4
IF temp% >= sqrt.num% THEN GOTO 3
GOTO 2
3 cur.prime.amount% = cur.prime.amount% + 1
prime%(cur.prime.amount%) = i%
4 IF i% = 32767 THEN GOTO 5
i% = i% + 2
GOTO 1
5 i2& = prime(cur.prime.amount%)
i2& = i2& + 2
biggest.prime& = i2&
i3# = TIMER + 1
6 j% = 1
sqrt.num% = SQR(i2&)
7 temp% = prime(j%)
IF i2& MOD temp% = 0 THEN GOTO 9
IF temp% >= sqrt.num% THEN GOTO 8
j% = j% + 1
GOTO 7
8 biggest.prime& = i2&
9 i2& = i2& + 2
IF TIMER > i3# THEN i3# = TIMER + 1: PRINT biggest.prime&
GOTO 6
'IF INKEY$ = "" THEN GOTO 6


Title: The PRIME NUMBERS
Post by: toonski84 on June 02, 2003, 03:39:56 PM
Well, i've always thought french kissing is better than regular kissing, so the possibility's certainly there... But then again, American cheese kicks ass, what with Wisconsin and all so I can't really say now.


Title: Re: And the Russians beat the French.
Post by: Mango on June 02, 2003, 05:09:03 PM
Nice job Agamemnus!!

I learned a bunch from your optimization of my code...Here's what I see from a quick look

goto faster than do:loop
putting an array element into a variable then calling that variable is faster than calling the array element repetedly
a^.5 is faster than squ(a)

any others that I missed?  Thanks again for the optimization.


Title: The PRIME NUMBERS
Post by: Antoni Gual on June 02, 2003, 05:44:18 PM
Agamemnus: You should review your code, some of the numbers printed end in 5 so they can't be primes...


Title: The PRIME NUMBERS
Post by: Agamemnus on June 02, 2003, 05:49:41 PM
Actually, SQR(x) is 2x faster than ^.5. I think that's because ^x uses a general method, and SQR(x) is a streamlined version of ^x, with a lot of things canceling out.

Your code is slower because:

1) You have a while loop for your timer
2) You use UNTIL instead of direct IFs...

Of course a good compiler will make ^.5 into SQR(x). But qb45.exe isn't actually that smart..


EDIT: You're right, I fouled up.
EDIT: Fixed...


Title: The PRIME NUMBERS
Post by: whitetiger0990 on June 02, 2003, 05:56:59 PM
I like my program that finds primes up to the number specified

Code:
CLS
INPUT n
FOR i = 1 TO n
a = i * 6 - 1
b = i * 6 + 1
IF a <= n THEN
z = 1
DO
  z = z + 1
  IF z = a THEN PRINT a: EXIT DO
  IF a / z = INT(a / z) THEN EXIT DO
LOOP
END IF
IF b <= n THEN
z = 1
DO
  z = z + 1
  IF z = b THEN PRINT b: EXIT DO
  IF b / z = INT(b / z) THEN EXIT DO
LOOP
END IF
NEXT


Title: The PRIME NUMBERS
Post by: Antoni Gual on June 02, 2003, 06:47:53 PM
Let's try it in the spanish way:
The best way to calculate a square root is not calculating it at all..
No divisions or MOD either..
It calculates 16384 primes in 3 seconds in my P4 1,4... to display them it takes a little longer.
Code:

CLS
PRINT "PRIME CALCULATOR BY ANTONI GUAL"
'indicate in stor how many primes you want
CONST stor = 16383 'That's the maximum;you may have to set the /ah switch
REDIM pr(stor) AS LONG
REDIM pr1(stor) AS LONG
REDIM pr2(stor) AS LONG

'pr saves primes found
'pr1 saves primes multiplied by factor pr2
'We save pr2 to stop scanning the array if pr2<pr, this indicates that
' pr> sqr(test&) without having to calculate the square root.
'
'pr() saves primes, pr1()=pr()*pr2()

'init the tables with 2 and test our first candidate, 3
pr(0) = 2
pr1(0) = 2
pr2(0) = 1
maxx& = 2
ind% = 0
test& = 3

t! = TIMER
DO
 isprime% = -1
 FOR i% = 0 TO ind%
   WHILE pr1(i%) < test&: pr1(i%) = pr1(i%) + pr(i%): pr2(i%) = pr2(i%) + 1: WEND
   IF pr2(i%) <= pr(i%) THEN EXIT FOR
   IF pr1(i%) = test& THEN isprime% = 0: EXIT FOR
 NEXT
 IF isprime% THEN
  ind% = ind% + 1
  IF (ind% AND 1023) = 0 THEN PRINT ind%; "th prime is:"; test&
  pr(ind%) = test&
  pr1(ind%) = test&
  pr2(ind%) = 1
 END IF
 test& = test& + 1
LOOP UNTIL ind% = stor

'That's all!

t1! = TIMER - t!
PRINT : PRINT stor + 1; " primes found in"; t1!; " seconds."; : INPUT "Want to print them all? (Y/N)"; a$
IF UCASE$(a$) <> "Y" THEN END

t! = TIMER
'array full, print it...
PRINT
FOR i% = 0 TO stor
  PRINT pr(i%),
NEXT
PRINT : PRINT stor + 1; " primes printed in "; TIMER - t!; "Not so fast..."

ERASE pr, pr1, pr2


Title: The PRIME NUMBERS
Post by: Agamemnus on June 02, 2003, 07:02:45 PM
i'm lost.


Title: Toonski
Post by: Mango on June 02, 2003, 08:32:55 PM
Quote from: "toonski84"
this works well enough for me.

Code:
INPUT number&

FOR y& = 1 TO number&
  prime% = 0
  FOR x& = 2 TO SQR(y&) - 1
    IF y& / x& = y& \ x& THEN prime% = 1
  NEXT x&
  IF prime% = 0 THEN PRINT y&
NEXT y&


I hope you don't think I picking on you...your code pegs 25, 49, and 121 as prime...all have prime roots, but they themselves are not prime...I hope this isn't good enough for you!!! :-?


Title: The PRIME NUMBERS
Post by: toonski84 on June 02, 2003, 08:42:32 PM
the world aint perfect....

hey, for pulling it out of me arse it worked okay, right?


Title: The PRIME NUMBERS
Post by: Antoni Gual on June 02, 2003, 08:48:49 PM
Well, actually I could do it faster:
-Limited size of tables so they fit in dgroup.
-Saves primes into a file so you can check them
-It displays one prime every 16000 so you can see it's working
-It calculates and saves 300,000 primes in 1 minute (compiled)
The highest prime it can calculate should be under 2^30, it makes around 5,000,000 primes. However,I have not patiented to see the end :D, it can take hours and probably it ends by an error.

Code:

CLS
PRINT "PRIME CALCULATOR BY ANTONI GUAL agual@eic.ictnet.es"
'Version 2.
CONST pp = 1024& * 16 - 1

CONST stor = 3400 'enough to calculate the 10,000,000 first primes
DIM pr(stor + 2) AS INTEGER
DIM pr1(stor + 2) AS LONG
DIM pr2(stor + 2) AS LONG
DIM ind AS LONG

'pr saves primes found
'pr1 saves primes multiplied by factor pr2
'We save pr2 to stop scanning the array if pr2<pr, this indicates that
' pr> sqr(test&) without having to calculate the square root.
'
'pr() saves primes, pr1()=pr()*pr2()

'init the tables with 3 and test our first candidate, 5
pr(2) = 3
pr1(2) = 3
pr2(2) = 1
maxx& = 2
ind = 2
test& = 5

t! = TIMER
OPEN "primes.txt" FOR OUTPUT AS #1
PRINT #1, 2, 3,
DO
 isprime% = -1
 i% = 1
 DO
   i% = i% + 1
   WHILE pr1(i%) < test&: pr1(i%) = pr1(i%) + pr(i%): pr2(i%) = pr2(i%) + 1: WEND
   IF pr1(i%) = test& THEN isprime% = 0: EXIT DO
 LOOP UNTIL pr2(i%) <= pr(i%)
 IF isprime% THEN
  ind = ind + 1
  IF (ind AND pp) = 0 THEN PRINT USING "####### th prime is: ##########. Time:###.# sec."; ind; test&; TIMER - t!
  PRINT #1, test&,
  IF (ind AND 7) = 0 THEN PRINT #1,
  IF ind <= stor THEN
  pr(ind) = test&
  pr1(ind) = test&
  pr2(ind) = 1
  END IF
 END IF
 test& = test& + 2
LOOP UNTIL (i% = stor) OR LEN(INKEY$)
ERASE pr, pr1, pr2
CLOSE


Title: Antonio...re not using squareroots...
Post by: Mango on June 02, 2003, 09:21:06 PM
Quote from: "Antoni Gual"
Let's try it in the spanish way:
The best way to calculate a square root is not calculating it at all..
No divisions or MOD either..
It calculates 16384 primes in 3 seconds in my P4 1,4... to display them it takes a little longer.


Antonio...note that in my May 7 post, I used a similar method to avoid the sqrt issue ...using 2 different methods for the big primes and for the small primes:

1st
LOOP WHILE smallprimes(a) * smallprimes(a) < next1

2nd
LOOP WHILE (nextbig& \ smallprimes(a)) > smallprimes(a)

I used the 2nd method because the numbers got too big when the direct square was used.

However, when I tweaked the code a bit in my May 29 post...I used SQR...outside the loop.  which turned out to be faster.   Also, by using a separate array to hold the small primes you don't have the problem of overflow errors...and if you hold the small primes as integers (for the ones smaller than 32000) and use these to test the long integer primes, both save memory and gain on speed.  

OT...I looked at your file handling routines last week...thanks.

To the people just now posting their prime-finding methods...just to make sure we are all on the same page, as the recent methods haven't been printing all the primes (even though they were calculated), if you want to see if your method is a contender, make it print all primes using the semicolon...eg:
PRINT myprime&;
 
and compare the output to the output of the following code by Me and  Argamemnus:
In the iteration before this, the code just printed one prime every second...which is a convienient way to see the highest prime that will be printed in, say, 10 seconds.  However, this may be confusing to those just joining the fray...

I'm sure we'd all love to see a faster method than this...

Code:
DIM prime(1 TO 5000) AS INTEGER, cur.prime.amount AS INTEGER
cur.prime.amount% = 1
prime%(1) = 2
i% = 3
1 j% = 0
sqrt.num% = SQR(i%)
2 j% = j% + 1
temp% = prime%(j%)
IF i% MOD temp% = 0 THEN GOTO 4
IF temp% >= sqrt.num% THEN GOTO 3
GOTO 2
3 cur.prime.amount% = cur.prime.amount% + 1
prime%(cur.prime.amount%) = i%: PRINT i%;
4 IF i% = 32767 THEN GOTO 5
i% = i% + 2
GOTO 1
5 i2& = prime(cur.prime.amount%)
i2& = i2& + 2
biggest.prime& = i2&
6 j% = 1
sqrt.num% = SQR(i2&)
7 temp% = prime(j%)
IF i2& MOD temp% = 0 THEN GOTO 9
IF temp% >= sqrt.num% THEN GOTO 8
j% = j% + 1
GOTO 7
8 PRINT i2&;
9 i2& = i2& + 2
GOTO 6


Argamemnus...is this post OK that I give shared credit for the code?  If not, I'll erase the whole thing...

Cheers, and thanks for the tips, people.


Title: The PRIME NUMBERS
Post by: Antoni Gual on June 02, 2003, 09:37:58 PM
Well this one abides by all rules set by Touf:
-You can set the maximum prime you want
-It prints them all (after saving them into a file)
Code:

CLS
PRINT "PRIME CALCULATOR BY ANTONI GUAL agual@eic.ictnet.es"
INPUT "Maximum prime(1 to 1,000,000,000): "; mp&

CONST pp = 1024& * 16 - 1
CONST tabs = 10
CONST stor = 3400 'enough to calculate the 10,000,000 first primes
DIM pr(stor + 2) AS INTEGER
DIM pr1(stor + 2) AS LONG
DIM pr2(stor + 2) AS LONG
DIM ind AS LONG

'pr saves primes found
'pr1 saves primes multiplied by factor pr2
'We save pr2 to stop scanning the array if pr2<pr, this indicates that
' pr> sqr(test&) without having to calculate the square root.
'
'pr() saves primes, pr1()=pr()*pr2()

'init the tables with 3 and test our first candidate, 5
pr(2) = 3
pr1(2) = 3
pr2(2) = 1
ind = 2
test& = 5

t! = TIMER
OPEN "primes.txt" FOR OUTPUT AS #1
tt% = tt% + tabs: PRINT #1, 2; TAB(tt%);
tt% = tt% + tabs: PRINT #1, 3; TAB(tt%);
DO
 isprime% = -1
 i% = 1
 DO
   i% = i% + 1
   WHILE pr1(i%) < test&: pr1(i%) = pr1(i%) + pr(i%): pr2(i%) = pr2(i%) + 1: WEND
   IF pr1(i%) = test& THEN isprime% = 0: EXIT DO
 LOOP UNTIL pr2(i%) <= pr(i%)
 IF isprime% THEN
  ind = ind + 1
  IF (ind AND pp) = 0 THEN PRINT USING "####### th prime is: ##########. Time:###.# sec."; ind; test&; TIMER - t!
  tt% = tt% + tabs: PRINT #1, test&; TAB(tt%);
  IF (ind AND 7) = 0 THEN PRINT #1, : tt% = 0
  IF ind <= stor THEN
  pr(ind) = test&
  pr1(ind) = test&
  pr2(ind) = 1
  END IF
 END IF
 test& = test& + 2
LOOP UNTIL (i% = stor) OR test& > mp& OR LEN(INKEY$)
ERASE pr, pr1, pr2
CLOSE
'That's all!
OPEN "primes.txt" FOR INPUT AS #1
WHILE NOT EOF(1)
LINE INPUT #1, a$
PRINT a$
WEND
close
PRINT
PRINT "Total time "; TIMER - t!; "seconds. Results are in the file PRIMES.TXT"


Title: The PRIME NUMBERS
Post by: Touf on June 03, 2003, 06:07:14 AM
okay !
I'll chek your programs ( Antoni and Agamemnus ) , and I'll update the classification soon .


Title: The PRIME NUMBERS
Post by: Touf on June 03, 2003, 09:09:07 AM
hahaaaa !!!

Agamemnus , your program is quite good , but not enough !  :wink:

I didn't understand the subject of your post ... you said "And the russians beat the french" ???

Aren't you from USA ?


Title: WHAT! WheRE DID MY POST GO?
Post by: Agamemnus on June 03, 2003, 01:15:10 PM
anyways, it is ok to post it, Mango, since your method and mine are almost identical. But be warned! It won't work for any number greater than (the first prime number before 32767) squared!

google.com: primes: first entry: gives a good fast method of finding primes, but the algorithm is incomplete.

Touf: I was born in Moscow, Russia, but I live in the USA.


Title: The PRIME NUMBERS
Post by: Antoni Gual on June 03, 2003, 02:51:22 PM
As I said before the speed problem is not in calculating primes, it is in displaying them.
So there is a version of my algorithm that beats all, just avoiding screen scrolls. Unfortunately Agamemnus and Mango can do exactly the same thing and beat me again...
Code:

WIDTH , 50: CLS
PRINT "PRIME CALCULATOR BY ANTONI GUAL agual@eic.ictnet.es"
INPUT "Maximum prime(1 to 1,000,000,000): "; mp&
CONST pp = 1024& * 16 - 1
CONST tabs = 10
CONST stor = 3400 'enough to calculate the 10,000,000 first primes
DIM pr(stor + 2) AS INTEGER
DIM pr1(stor + 2) AS LONG
DIM pr2(stor + 2) AS LONG
DIM ind AS LONG
pr(2) = 3
pr1(2) = 3
pr2(2) = 1
ind = 2
test& = 5
t! = TIMER
PRINT 2, 3,
CNT% = 2
DO
 isprime% = -1
 i% = 1
 DO
   i% = i% + 1
   WHILE pr1(i%) < test&: pr1(i%) = pr1(i%) + pr(i%): pr2(i%) = pr2(i%) + 1: WEND
   IF pr1(i%) = test& THEN isprime% = 0: EXIT DO
 LOOP UNTIL pr2(i%) <= pr(i%)
 IF isprime% THEN
  ind = ind + 1
  PRINT test&,
  CNT% = CNT% + 1: IF CNT% = 250 THEN CLS : CNT% = 0
  IF ind <= stor THEN
  pr(ind) = test&
  pr1(ind) = test& + test&
  pr2(ind) = 2
  END IF
 END IF
 test& = test& + 2
LOOP UNTIL (i% = stor) OR test& > mp& OR LEN(INKEY$)

ERASE pr, pr1, pr2
PRINT : PRINT : PRINT "time for "; ind; "primes:"; TIMER - t!; ""
a$ = INPUT$(1)


Title: The PRIME NUMBERS
Post by: toonski84 on June 03, 2003, 03:04:03 PM
hey!? where did my post go?

I left my computer on running your program last night dav... It went up and over 14,000,000 primes somehow.


Title: The PRIME NUMBERS
Post by: Agamemnus on June 03, 2003, 03:10:05 PM
I saw your post, with a New York Times window or something in the background. My post disappeared too.

"The case of the disappearing posts"!  :o


Title: The PRIME NUMBERS
Post by: toonski84 on June 03, 2003, 03:16:54 PM
I smell an admin behind this!!  Will Joe and Agamemnus find the masked post-deleter?  Can this madman be stopped??  Will Aunt Harriot stumble across our hero's secret identity??  Tune in tomorrow, same Bat-time, same Bat-channel!


Title: The PRIME NUMBERS
Post by: ak00ma on June 03, 2003, 04:04:40 PM
The MATRIX gonna get you

 8)


Title: The PRIME NUMBERS
Post by: Touf on June 03, 2003, 04:18:50 PM
Antoni , is this the program you mailed me ?

If not , mail me your last version please !


Title: The PRIME NUMBERS
Post by: Antoni Gual on June 03, 2003, 05:01:03 PM
Touf: Check your e-mail


Title: The PRIME NUMBERS
Post by: Agamemnus on June 03, 2003, 05:43:30 PM
there is stuff missing in other sections, too!!!!

EDIT: Projects section.


Title: The PRIME NUMBERS
Post by: whitetiger0990 on June 03, 2003, 05:52:43 PM
where?


Title: The PRIME NUMBERS
Post by: Neo on June 04, 2003, 06:42:01 AM
Quote from: "toonski84"
I left my computer on running your program last night dav... It went up and over 14,000,000 primes somehow.


Whow! 14,000,000! Not bad :)

Mine got till the LONG overflow, that is up to and including 7FFFh ;)
And just in 1,5 hour


Title: The PRIME NUMBERS
Post by: Mango on June 04, 2003, 11:48:17 AM
Quote from: "Neo"
Mine got till the LONG overflow, that is up to and including 7FFFh ;)
And just in 1,5 hour


That's pretty good.  What's your method?  I just compiled a slightly modified version (doesn't poll the timer, instead prints a prime every 64 k found) of mine and it's running in a background window on a 1.5 GHz machine...it's been on for a whopping 7 min 20 sec and the most recent prime is 19,562,177...at this rate, mine's not set to overflow the long integer until about 13 hrs.  

I'd like to see your method...it kicks my methods ass.  Is it a method that picks primes with high probability, or does it exhastively prove each prime?  Anyway...we're up to 11 min, 30 sec and latest prime is.... 27,033,163...

edits:
36 min...60,193,877
3 h 41 min...240,677,251


Title: The PRIME NUMBERS
Post by: Antoni Gual on June 04, 2003, 08:13:46 PM
Mango:
First of all your method is faster than your results. You should leave the computer runing your compiled program alone in the foreground. This way you should reach the long overflow before 4 hours.
And the 1,5 hour could be reached by the program by Rich Geldreich you posted when this challenge started (you said clearly you did'nt write it). I have no patience to check it but it could reach the limits in 1,5 hour as Neo says. Remember i'ts a program ported from the computer bible "The Art of Computer Programming" so it should be good. By the way , could someone explain me how does it work?

Edited:
About speed, don't forget there are AMD processors abe to run 16 bits apps 3 times faster than a P4 1,5...Any speed comparison should be done in the same computer!


Title: The PRIME NUMBERS
Post by: Agamemnus on June 04, 2003, 08:19:03 PM
It checks every odd number for primality by seeing if it is evenly divisible by every number that is less than 32767.

The reason is that it is slower to do mod using integers, but you can only check up to 32761 (I think it's a prime) squared.

A number can be checked for primality by just doing mod all primes less than the square root of that number because you just check the same numbers over again after...

(x+1)(x-1)
(x-1)(x+1)


Title: The PRIME NUMBERS
Post by: Neo on June 05, 2003, 04:12:11 AM
Quote from: "Mango"
Quote from: "Neo"
Mine got till the LONG overflow, that is up to and including 7FFFh ;)
And just in 1,5 hour


That's pretty good.  What's your method?  I just compiled a slightly modified version (doesn't poll the timer, instead prints a prime every 64 k found) of mine and it's running in a background window on a 1.5 GHz machine...it's been on for a whopping 7 min 20 sec and the most recent prime is 19,562,177...at this rate, mine's not set to overflow the long integer until about 13 hrs.  

I'd like to see your method...it kicks my methods ass.  Is it a method that picks primes with high probability, or does it exhastively prove each prime?  Anyway...we're up to 11 min, 30 sec and latest prime is.... 27,033,163...

edits:
36 min...60,193,877
3 h 41 min...240,677,251


It wasn't made in QB :). However, these are the test results with my program made in QB:

1 min: 2,000,000
2 min: 4,031,482
1 h: 240,482,843

The programming algorithm was the Sea of Erathetos. However, there are much faster algorithms :)


Title: The PRIME NUMBERS
Post by: Antoni Gual on June 06, 2003, 11:01:24 AM
This one is a 30% faster than my former post
Code:

WIDTH , 50: CLS
PRINT "PRIME CALCULATOR BY ANTONI GUAL agual@eic.ictnet.es"
INPUT "Maximum prime(5 to 2,100,000,000): "; mp&
CONST stor = 3400 'enough to calculate the 5,000,000 first primes

DIM pr(stor) AS LONG   'keeps  2 * prime (the increment to next multiple)
DIM pr1(stor) AS LONG  'keeps the current muliple of the prime

'seed the tables
pr(2) = 2 * 3
pr1(2) = 3 * 3

'init vars
ind& = 2
ind2% = 2
sqre& = 5 * 5

'first prime tested
test& = 5
'just a trick to avoid W2000 to lower priority
OPEN "nul" FOR OUTPUT AS #1
t! = TIMER
PRINT 2, 3,
CNT% = 2
DO
  i% = 1
  DO
    i% = i% + 1
    WHILE pr1(i%) < test&: pr1(i%) = pr1(i%) + pr(i%): WEND
    IF pr1(i%) = test& THEN GOTO noprime
  LOOP UNTIL i% = ind2%
  'it's a prime, print it
  ind& = ind& + 1
  PRINT test&,
 
  'scroll screen if needed (And keep priority high in W2000)
  CNT% = CNT% + 1: IF CNT% = 250 THEN CLS : CNT% = 0: PRINT #1, ".";
 
  'add to primes table
  IF ind& <= stor THEN : pr(ind&) = test&: IF ind2% = stor THEN EXIT DO

noprime:
  'go for next prime
  test& = test& + 2
 
  'if beyond square of last divisor, add a new divisor to tests
  IF test& > sqre& THEN
    ind2% = ind2% + 1: sqre& = pr(ind2%) * pr(ind2%)
    pr1(ind2%) = sqre&
    pr(ind2%) = pr(ind2%) + pr(ind2%)
    IF LEN(INKEY$) THEN EXIT DO
  END IF
LOOP UNTIL test& > mp&

''STOP
ERASE pr, pr1
PRINT : PRINT : PRINT "time for "; ind&; "primes: "; TIMER - t!; "seconds"
a$ = INPUT$(1)



I'm now  figuring out how to sort my arrays, it should be even faster


Title: The PRIME NUMBERS
Post by: Joakim on June 07, 2003, 06:21:16 PM
This one is really neat. It's fast and it's small.

Code:
FOR i& = 0 to 2147483647
  PRINT i&
NEXT


Now, don't tell me it doesn't print out all the prime numers  :P


Title: The PRIME NUMBERS
Post by: Agamemnus on June 07, 2003, 08:25:25 PM
LOOPHOLE!


Title: The PRIME NUMBERS
Post by: Antoni Gual on June 08, 2003, 10:20:23 AM
I should have had that idea...


Title: The PRIME NUMBERS
Post by: whitetiger0990 on June 08, 2003, 08:34:57 PM
This finds primes. But slowly. Antoni Gual i need to look at your prog to find an easier way to tell of a number isn't prime.

Code:
CLS
WIDTH , 50
INPUT pm
t = TIMER
FOR p = 3 TO pm STEP 2
 FOR i = 2 TO p - 1
  IF p / i = INT(p / i) THEN np = 1: EXIT FOR
 NEXT i
 IF np = 1 THEN np = 0 ELSE r = r + 1: PRINT p, : r2 = r2 + 1
 IF r2 = 5 THEN r2 = 0: r = r + 1:
 IF r = 250 THEN r = 0: CLS
NEXT p
PRINT : PRINT : PRINT USING "####.##"; TIMER - t


Title: The PRIME NUMBERS
Post by: Antoni Gual on June 08, 2003, 09:01:28 PM
This is the faster I can do. It uses a priority queue to keep the multiples array ordered. I learned about this useful construction by participating there, so I thank you all for that.:D

Code:

WIDTH , 50: CLS
CONST maxlng = &H7FFFFFFF
PRINT "PRIME CALCULATOR BY ANTONI GUAL agual@eic.ictnet.es"
DO
PRINT "Maximum prime(5 to "; maxlng; "): "; : INPUT mp&
LOOP UNTIL mp& >= 5 AND mp& <= maxlng

CONST stor = 4750

DIM pr(stor + 1) AS LONG
DIM pr1(stor + 1) AS LONG

pr(1) = 2 * 3
pr1(1) = 3 * 3

ind& = 1
ind2% = 1
pr1(2) = maxlng
sqre& = 3 * 3

test& = 5
OPEN "nul" FOR OUTPUT AS #1
t! = TIMER
PRINT 2, 3,
CNT% = 2
DO
  DO
    a& = pr1(1)
    IF a& >= test& THEN EXIT DO
    b& = pr(1)
    a& = a& + b&
    i% = 1
    DO
      j% = i% + i%
      IF j% > ind2% THEN EXIT DO
      IF pr1(j%) > pr1(j% + 1) THEN j% = j% + 1
      IF a& <= pr1(j%) THEN EXIT DO
      pr(i%) = pr(j%)
      pr1(i%) = pr1(j%)
      i% = j%
    LOOP
    pr1(i%) = a&
    pr(i%) = b&
  LOOP
  IF a& > test& THEN
    ind& = ind& + 1
    PRINT test&,
    'the print #1 "." is just for W2000, you can erase it if you want
    CNT% = CNT% + 1: IF CNT% = 250 THEN CLS : CNT% = 0: PRINT #1, ".";
    IF ind& <= stor THEN pr(ind&) = test&: IF ind2% = stor THEN EXIT DO
  END IF
  test& = test& + 2
  IF test& > sqre& THEN
    GOSUB addnew
    IF LEN(INKEY$) THEN EXIT DO
  END IF
LOOP UNTIL test& > mp&

PRINT : PRINT : PRINT "time for "; ind& + 1; "primes: "; TIMER - t!; "seconds"
a$ = INPUT$(1)
END

addnew:
    ind2% = ind2% + 1
    a& = pr(ind2%)
    sqre& = a& * a&
    j% = ind2%
    DO
      i% = j% \ 2
      IF i% = 0 THEN EXIT DO
      IF pr1(i%) <= sqre& THEN EXIT DO
      pr(j%) = pr1(i%)
      pr1(j%) = pr1(i%)
      j% = i%
    LOOP
    pr1(j%) = sqre&
    pr(j%) = a& + a&
    pr1(j% + 1) = maxlng
RETURN


The person that started this, Touf seems to have vanished in the air, his contest site has not been updated in a week. So who's the judge?....


Title: The PRIME NUMBERS
Post by: oracle on June 08, 2003, 09:12:21 PM
Hmmm, I do have a question. Is it possible to make a prime searching routine that checks numbers in strings, like those produced by BIGINT, BIGNUM (and StatLib when it arrives)? You know, numbers larger than can normally be handled by the traditional data types, 2000!-1 for example.


Title: The PRIME NUMBERS
Post by: Antoni Gual on June 08, 2003, 09:45:05 PM
Oracle:
This is a different problem than finding all primes up to a number.

AFAIK, to check if a number is prime you must check if it's divisible by some prime from 2 to the suare root of the number.
It means if your number is 2^62 you must have all the primes from 2 to 2^31 in a table. There are aproximately 100 million primes in that range. You coud calculate them previously and save them in a table. Rich Geldreich's progam generates in 1 hour such a table and stores it in a compressed format, 1 byte per prime but be aware  the table is 100 Meg in size...
A less bloated approach would be to divide by every number from 2 to square root of n, it would work but it would be very inefficient.


Title: The PRIME NUMBERS
Post by: oracle on June 08, 2003, 09:46:37 PM
It was just an idea for StatLib, maybe I'll add such a searcher in a later version, I can't be bothered coding such a thing now.


Title: The PRIME NUMBERS
Post by: Agamemnus on June 08, 2003, 10:59:30 PM
No, to check if a number is prime, you do NOT have to check from 2 to that number ^ .5. google.com: "primes", first entry.


Title: The PRIME NUMBERS
Post by: whitetiger0990 on June 08, 2003, 11:24:39 PM
Code:
CLS
WIDTH , 50
p = 3
t = TIMER
DO

 FOR i = 2 TO SQR(p)
  IF p / i = INT(p / i) THEN np = 1: EXIT FOR
 NEXT i

 IF np = 1 THEN
  np = 0
 ELSE
  IF c = 1 THEN c = 0:  PRINT USING "Time: ####.##"; TIMER - t: PRINT : LOCATE 1, 1
  PRINT p,
  c = c + 1
  pn = pn + 1
 END IF
 p = p + 2

LOOP UNTIL LEN(INKEY$) = 1

PRINT
PRINT
PRINT pn; " primes found"
PRINT USING "In ####.## sec"; TIMER - t


Antoni Gual: I was testing both of ours on primes up to 100000

Antoni Gual: 1 sec, found 9593 primes
Mine: 8 sec, found 9591 primes

one of ours is messed up. and im gussing it's mine.


Title: The PRIME NUMBERS
Post by: Agamemnus on June 08, 2003, 11:30:34 PM
You didn't store anything. He did.


Title: The PRIME NUMBERS
Post by: whitetiger0990 on June 08, 2003, 11:36:36 PM
So you saying that i forgot two primes? or did he happen to find two just laying on the ground.


Title: The PRIME NUMBERS
Post by: Agamemnus on June 09, 2003, 03:07:18 PM
Well, you didn't count the first prime (2) and the last one, probably.

I was talking about actually going through primes, not every number, like you did..... the reason why yours is slower.


Title: The PRIME NUMBERS
Post by: Mango on June 09, 2003, 03:39:05 PM
Quote from: "Joakim"
This one is really neat. It's fast and it's small.

Code:
FOR i& = 0 to 2147483647
  PRINT i&
NEXT


Now, don't tell me it doesn't print out all the prime numers  :P



That's pretty good...this one's more than twice as fast though!!!

Code:

PRINT "2";

FOR x& = 3 to 2147483647 STEP 2
PRINT x&;
NEXT x&


Title: The PRIME NUMBERS
Post by: Antoni Gual on June 09, 2003, 03:53:39 PM
whitetiger:
The two programs, yours an mine  are both not counting correctly the number of primes they display. You display 2 and don't count it. I don't display 1 (it can't be considered a prime, actually) but i count it. So there is the difference.


Title: The PRIME NUMBERS
Post by: whitetiger0990 on June 09, 2003, 04:55:54 PM
Code:

CLS
WIDTH , 50
p = 2
t = TIMER
DO

FOR i = 2 TO SQR(p)
  IF p = 2 THEN EXIT FOR
  IF p MOD i = 0 THEN np = 1: EXIT FOR
NEXT i

IF np = 1 THEN
  np = 0
ELSE
  'IF c = 1 THEN c = 0:  PRINT USING "Time: ####.##"; TIMER - t: PRINT : LOCATE 1, 1
  PRINT p, :  PRINT USING "Time: ####.##"; TIMER - t: PRINT : LOCATE 1, 1
  'c = c + 1
  pn = pn + 1
END IF
IF p = 2 THEN p = 3 ELSE p = p + 2

LOOP UNTIL p >= 100000'LEN(INKEY$) = 1

PRINT
PRINT
PRINT pn; " primes found"
PRINT USING "In ####.## sec"; TIMER - t


Print and counts number 2


Title: The PRIME NUMBERS
Post by: oracle on June 09, 2003, 10:11:27 PM
antoni: just take one from your result then.


Title: The PRIME NUMBERS
Post by: Antoni Gual on June 10, 2003, 07:01:10 PM
Yes, I should do it. I was just using a program that counts 1 as prime as speed reference while developing mine . I just forgot to  modify it before posting.


Title: The PRIME NUMBERS
Post by: Mango on June 13, 2003, 04:55:13 AM
Quote from: "Neo"
Mine got till the LONG overflow, that is up to and including 7FFFh ;)
And just in 1,5 hour


It wasn't made in QB :). However, these are the test results with my program made in QB:

1 min: 2,000,000
2 min: 4,031,482
1 h: 240,482,843



Hey Neo...I'm fiddling with C the last couple days...here's a c port of my basic primer finder...on my 1.5 GHz after 6 min, the biggest prime was 190,976,059.  This looks similar to what you reported re flipping the signed 4-byte int after 1.5 hr...Mine uses unsigned, so I get to go all the way to ffffffff, instead of cutting short at 7fffffff.  Cheers.

Code:
#include <iostream>

using namespace std;

int main()
{
    unsigned short inc = 1;
    unsigned long c;
    unsigned long x;
    unsigned long stop;
    unsigned long count=0;
    unsigned long hold=1;
    unsigned short array[6540]={3};
       
   
    cout << "Find primes up to what number?  (4,200,000,000 max)\n";
    cin >> stop;
   
    for (x=3; x<65536;x += 2)  //get small primes, put in array
    {      
        for (c=0; (x % array[c]) && (array[c]*array[c] < x)  ; c++);
        if (x % array[c])
        {
             //cout << x << " ";   //use this line to show all primes
             array[inc++]=x;
        }  
    }
   
    for (x=65537; x<stop;x += 2)  //find large primes
    {
        for (c=0; (x % array[c]) && (array[c]*array[c] < x)  ; c++);
        if (x % array[c])
        {
             //cout << x << " ";   //use this line to show all primes
             if (count++ > hold)
             {
             cout << x << " ";     //print every 100000th prime
             hold += 100000;
             }
        }  
    }
           
    cout << "\n done\n";
    return 0;
}