Tutorial 027 Primes

The following program is has been adapted from one in "Further Programming for the BBC Micro" by Alan Thomas, by omitting line numbers and using the multiline IF....THEN....ENDIF statement instead of a GOTO available in BB4W.

Its certainly not easy to see immediately how it works, but this program certainly pumps out the primes at a rate of knots....
Gulberg in "From the Birth of Numbers" summarises this method - the Sieve of Eratosthenes - as follows:

"In a series of natural numbers, beginning with 2, start by striking out every second number after 2 - this eliminates every multiple of 2. Next delete every third number after 3, then every fourth number after 4 etc. Several numbers will be cancelled more than once. The numbers left standing are the prime numbers; those struck out are composite".

      REM: Primes
      REM: Richard Weston 26 May 2003
      REM: after Alan Thomas 1982
      MODE0
      @%=5
      n=1700
      d=(2*n)+3
      DIM a(n)
      PRINT "Primes less than ";d
      FOR i=2 TO 3: PRINTi;:NEXT i
      j=0:t=3
      REPEAT
        FOR L=t TO d STEP 2*t
          a((L-3)DIV 2)=1
        NEXT L
        FOR i=j TO n
          sw=0
          IF a(i)<>1 THEN
            sw=1
            j=i
            t=2*i+3
            i=n
            PRINT t;
          ENDIF
        NEXT i
      UNTIL sw=0

Annotated listing :

REM: Primes
      REM: Richard Weston 26 May 2003
      REM: after Alan Thomas 1982
      MODE0
      @%=5 *** print formatting ***
      n=1700 *** chosen to fill just one screen - reduce if memory a problem ***

      d=(2*n)+3
*** the highest number to be checked for "primeness"- N.B. odd numbers need only be considered ***

      DIM a(n) *** array to hold the numbers to be checked ***

      PRINT "Primes less than ";d

      FOR i=2 TO 3: PRINTi;:NEXT i
*** 2 and three are just taken as read to avoid unnecesary steps ***

      j=0 : t=3
*** j is the start number in a checking run ***
*** t is the (previous) prime number found ***

      REPEAT
*** main loop - continues until all numbers in the range have been encountered ***

        FOR L=t TO d STEP 2*t
*** L is the number in the series to be discounted from primality - it is "struck out" by labelling its location with a one***
*** STEP 2*t because the intermediate values found using "STEP t" would be even and therefore already discounted ***
          a((L-3)DIV 2)=1
*** The (L-3)DIV 2)th array location holds this value of L

        NEXT L

        FOR i=j TO n
*** Loop goes from the last prime onto the next (if there is one) ***

          sw=0
*** a flag, (used to detect the end of the whole process when a prime is not met), is unset ***

          IF a(i)< >1 THEN
*** the number specified by this location is prime - its not already been struck out! ***

            sw=1
*** flag is set when a prime is found ***

            j=i
*** starting value for the next time round the main loop ***

            t=2*i+3
*** the (prime) number t corresponding to memory location i ***

            i=n
*** setting i=n means the FOR.... NEXT loop will terminate immediately ***

            PRINT t;
*** Print the newly found Prime Number ***

          ENDIF

        NEXT i

      UNTIL sw=0
*** You only get to here when no more prime numbers are found in the range specified ***

Next Tutorial

Richard Weston's Homepage