# Qbasicnews.com

Full Version: The PRIME NUMBERS
You're currently viewing a stripped down version of our content. View the full version with proper formatting.
Pages: 1 2 3 4 5 6 7
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 ....

This is a NO TIME LIMIT contest !
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 emailed mine...
Please , send your programs by e-mail , then I'll be able to upload my website .
Thanx
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 !
Quote: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!!!
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%```
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.
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.
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)?
Pages: 1 2 3 4 5 6 7