Prime Number Finder

[Pr0fess0r]

How would you adjust this program to allow it to search though numbers higher than 32767. I just use an array to store if a number is prime or not, but once the array fills up that's just as far as it can go. Is there a way to use multiple array's or would I have to save if a number is prime or not to a file. Whatever you think is the best method of correcting it, enlighten me.

-----------------------------------------------------------------------------

CLS
INPUT "The highest number to go to"; maxnum%
time1! = TIMER
DIM array%(maxnum%)
FOR i% = 2 TO maxnum%
array%(i%) = 1
NEXT i%
FOR prime% = 2 TO SQR(maxnum%)
IF array%(prime%) = 1 THEN
FOR i% = 2 TO (maxnum% \ prime%)
array%(i% * prime%) = 0
NEXT i%
END IF
NEXT prime%
FOR prime% = 2 TO maxnum%
IF array%(prime%) = 1 THEN
PRINT prime%,
count = count + 1
END IF
NEXT prime%
time2! = TIMER
time! = time2! - time1!
PRINT
PRINT "This algorithm took a mere "; time!; " seconds."
PRINT "There are"; count; "prime numbers to"; maxnum%
INPUT "Would you like to go though the primes in sections"; choice$
IF choice$ = "yes" THEN GOTO yes:
end
yes:

FOR i% = 2 TO maxnum%
IF array%(i%) = 1 THEN
PRINT i%,
count1 = count1 + 1
END IF
IF count1 = 110 THEN
SLEEP
count1 = 0
END IF
NEXT i%
PRINT
PRINT "Finished"
SLEEP
END

[Neo]

A function I made for KetOn a very long while ago:

[syntax="QBasic"]'##############
' Sea Function
'##############
SUB KT.PRIME.Erathetos (ArrayToFill() AS INTEGER, StartNumber AS LONG)
'Erathetos function, By Neo Deus Ex Machina
endnumber& = UBOUND(ArrayToFill) + StartNumber 'calculate the last number to check
begNumber& = StartNumber \ 2
IF begNumber& < 2 THEN begNumber& = 2
FOR i& = 0 TO UBOUND(ArrayToFill) 'fill the array with &HFFFF
ArrayToFill(i&) = -1
NEXT i&
loopto& = endnumber& \ 2 'last loop number
FOR i& = 2 TO loopto&
begNumber& = StartNumber \ i&
IF begNumber& < 2 THEN begNumber& = 2
FOR inloop& = begNumber& TO endnumber& \ i&
multiplication& = inloop& * i& 'this is no prime
IF multiplication& >= StartNumber THEN ArrayToFill(multiplication& - StartNumber) = 0 'put in array that this is no prime
NEXT inloop&
NEXT i&
END SUB[/syntax]

[Antoni Gual]

To go beyond 32767 you must first convert some variables to long, then you have diferent options.

-Save the primes to a file. You should keep in memory the primes up to the square root of the maximum prime, to avoid having to read them back from the file.

-Use an array of bits (each bit represents a number, 1 means prime, 0 means composite) this way you can go up to 32767*16. In fact you can go up to 32767*32 if you skip the even values.

-If you are using QB4.5 you can load it with the /AH switch, so it can work with arrays bigger than 64K. Then use REDIM instead of DIM to dimension your array. (the indexes are still limited to +/-16327 but you can make arrays of longs).

In any case you are interested in getting rid of the products in inner loops if you don't want the calculation last forever.
The following algorithm calculates primes up to 10^8 in 3 minutes

Code:

'--------------------------------------------------------------------------------
'Prime number generator by Rich Geldreich 1992
'Ported to FB by Antoni Gual 2005
'Method Suggested by D.Knuth in TAOCP Vol Sort and Search
'-Uses a 'sliding window' sieve combined with a priority queue.
'-Skips multiples of 2 and multiples of 3.
'-Builds a compressed list of primes saving  the gaps/2, so each
'  prime takes only 1 byte in the file.
'-AG modified: Factors waiting to enter the queue are saved in the
'  unused part of the array, not in the file as Rich did.
'---------------------------------------------------------------------------------
' P4 2,4  primes up to 10^9      FB    121 sec      DevC 107 sec
'                      10^8      QB4.5 184 sec
'---------------------------------------------------------------------------------
'Note: Atkin sieve calculates primes up to 10^9 in 6 seconds
'---------------------------------------------------------------------------------
DEFINT A-Z

CONST HeapSize = 9000

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

DIM dd AS string*1
DIM SHARED lastprime&
DIM SHARED TT!
DIM HeapQ(1 TO HeapSize) AS LONG
reDIM HeapQ1(1 TO HeapSize) AS LONG
reDIM HeapQ2(1 TO HeapSize) AS LONG
DIM mprime&
DIM SHARED candid 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, d AS LONG
DIM r AS INTEGER, r2 AS INTEGER, i AS INTEGER, j AS INTEGER, cnt&, a AS INTEGER, b AS INTEGER
DIM k$

'Initialize it
lastprime& = 5
cnt& = 3
d = 4
r = 1
r2 = r + 1
t = 25
HeapQ(1) = 25
HeapQ1(1) = 10
HeapQ2(1) = 30

candid = 7


INPUT "Max prime:"; mprime&
TT! = TIMER
'main loop
DO
  'Advance the window making all factors bigger or equal than the   candidate
'and sorting them, the smaller first
  DO
    Q = HeapQ(1)
    Q1 = HeapQ1(1)
    Q2 = HeapQ2(1)

    TQ = Q + Q1
    TQ1 = Q2 - Q1

    i = 1
    DO
        j = i+i
        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 candid <= Q

  'all candidates up to the first factor are primes
  DO WHILE candid < Q
  ' save to file one half of the diference to previous prime
    lset dd=chr$((candid-lastprime&) \2)
    PUT #1, , dd
    lastprime& = candid
     cnt& = cnt& + 1
    'if (cnt& and &h1fFFF)=0 then locate 2,1: print cnt&;" primes ";candid
    IF r2 <= HeapSize THEN
      HeapQ(r2) = candid
      r2 = r2 + 1
    END IF
    candid = candid + d
    d = 6 - d
  LOOP
'if candidate equals the square of the biggest factor, add a new factor to the queue

  IF candid = t THEN
    u = HeapQ(r + 1)
    t = u * u
    'sort it to place
    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) =  u *2
    ELSE
      HeapQ1(j) =  u *4
    END IF
    HeapQ2(j) = 6 * u

    r = r + 1

  END IF
  'go for the first candidate bigger than the factor at the top of the queue
  candid = candid + d
  d = 6 - d

LOOP UNTIL r >= HeapSize OR candid > mprime&
CLOSE #1
PRINT cnt&; " primes in "; TIMER - TT!; " seconds"
SLEEP
END

[Pr0fess0r]

Thanks a lot, im starting to understand the many ways of finding primes. However Neo, our programs are very similar but I can't get yours to run and find numbers greater than can be held in one array. I just started into Qbasic a couple weeks ago, and since the class im in can't get past the input command I thought that I would go ahead and explore what Qbasic has to offer. Could you show me how you run your sub to find large primes, and that would probably help me fix my program. Thanks everyone for the help, a truely great forum, I might be on later tonight. Yet, since I have a headache and a pile of homework I might not get around to checking back until tommorow.

Until then,
Pr0fess0r

[anonjondoe]

Hi there,

I just saw this and thought I might post my prime number finder. It probably isn't as good as any of yours but from what I've seen it seems simpler.

Code:

CLS
DO
yes% = 0
INPUT "Number: ", number%
FOR X = 2 TO number% - 1
IF number% MOD X = 0 THEN
PRINT "THAT IS NOT A PRIME NUMBER!"
X$ = STR$(X)
PRINT "IT IS DIVISIBLE BY " + X$
yes% = 1
EXIT FOR
END IF
NEXT
IF yes% <> 1 THEN
PRINT "THAT IS A PRIME NUMBER!"
END IF
SLEEP
LOOP UNTIL INKEY$ = CHR$(27)

Hope this helps.

Jack :-)

[shiftLynx]

Every number that is not prime is divisible by one or more primes. You only need to keep an array of the prime numbers you have found so far; for each number after that, if you cannot divide it by any of the primes you've found before it, that number is also a prime, so you add it to the list.

Just start with the prime list containing '2'. This now means you are able to find up to 32767 different prime numbers, rather than just search 32767 numbers for primes.

[Quibbler]

I tried Antoni's program (above) but it seems to take forever doing to 10^8 (too much disc read/write). And takes 20 secs for 1 million. The program below takes 4 seconds to search to 1 million.
(on a 166 MHz)

Code:

REM finding primes to 1 million!!!
TT = TIMER
DEFLNG I-L
DIM A(0 TO 16300) AS LONG
DIM B(0 TO 30) AS LONG
B(0) = 1
FOR I = 1 TO 30
B(I) = B(I - 1) + B(I - 1)
NEXT I
FOR J = 2 TO 500
J1 = J \ 31: J2 = J MOD 31
IF (A(J1) AND B(J2)) = 0 THEN
K1 = J + J - 1
K2 = K1 * J - K1 + J
FOR I = K2 TO 500000 STEP K1
I1 = I \ 31: I2 = I MOD 31
A(I1) = (A(I1) OR B(I2))
NEXT I
END IF
NEXT J
REM *** End of main routine - Printout starts here ***
PRINT TIMER - TT: INPUT x$
PRINT " 2 ";
FOR I = 2 TO 500000
I1 = I \ 31: I2 = I MOD 31
L = A(I1) AND B(I2)
IF L = 0 THEN
PRINT I + I - 1;
K = K + 1
L1 = L1 + 1
IF K = 200 THEN x$ = INPUT$(1): K = 0
END IF
NEXT I
PRINT "Number of primes to 1M = "; L1 + 1

[shiftLynx]

[syntax="freebasic"]
option explicit

const MAX_PRIMES = &hffffff

dim primes(0 to MAX_PRIMES) as long
dim current as long
dim check as long
dim numPrimes as long
dim foundNewPrime as integer

primes(0) = 2
numPrimes = 1
for current = 3 to MAX_PRIMES step 2

' check whether the current number is divisible by any of the
' prime numbers that we've found so far.
foundNewPrime = 1
for check = 0 to numPrimes - 1
if current mod primes(check) = 0 then
foundNewPrime = 0
exit for
end if
next check

' this number couldn't be divided by any primes, therefore it
' is prime.
if foundNewPrime = 1 then
primes(numPrimes) = current

print current

' make sure we're not going too far.
if numPrimes = MAX_PRIMES then
print "found too many primes! the last prime was " + ltrim$(str$(current))
print "Press a key to quit..."
while inkey$ = "": wend
end
end if

numPrimes = numPrimes + 1
end if

next current

print "I found " + ltrim$(str$(numPrimes)) + " prime numbers between 0 and " + ltrim$(str$(MAX_PRIMES))

print "Press a key to quit..."
while inkey$ = "": wend

[/syntax]

[edit: bugfix]
[edit2: improved since no primes are even]

[Z!re]

FB:

Code:

highnum = 10000000        'Change here as you like



lownum = 3  'Do not change.
dim primbuff(highnum) as ubyte

num = 2
FOR N = lownum TO highnum STEP 2
    IF INKEY$ = CHR$(27) THEN END
    
    g = primbuff(n)
    
    IF g = 0 THEN
        Delta = 2 * N
        LOCATE 1, 1: PRINT "Current:"; N
        print "Found:";num
        FOR I = 3 * N TO highnum STEP Delta
            primbuff(i) = 1
        NEXT
        num&= num + 1
    ELSE
        dist = dist + 1
        pitch = pitch - 1
    END IF
NEXT

sleep

Can be modified to use a file instead of an array.

[Antoni Gual]

The Rich Geldreich's routine I posted works fast if:
-You use Freebasic
-You have a proper disk caching (as Windows provides) . Perhaps yo have it disabled.
The routine is fairly fast and uses a surprisingly low amount of memory.

If you are working in QB, you may want to reduce the array size, so you can make it STATIC, but it limits the ceiling of the search.

You can find original RG's version in the ABC packets http://www.qbasicnews.com/abc/showsnippe...snippet=21
It had a buffered disk access that made it faster in QB (no difference in FB so I removed it)

And you could implement the Atkin Sieve in QB, it's a huge program that in itsoriginal version in C calculates primes up to 4E9 in...3 (three!!) seconds in a P4 2,4. Only it is pages and pages of code without comments...

EDITED: i remembered this thread too http://forum.qbasicnews.com/viewtopic.ph...ght=#98973