Prime Numbers and BASIC

I am reading Godel, Escher, Bach: An Eternal Golden Braid by Douglas R. Hofstadter.  First published in 1979, the author discusses various systems – mathematical, visual and musical, which somehow manage to talk about themselves.  This self-reference, says the author, is one of the key ingredients for intelligence.
Much of the book so far has been taken up with explaining some key elements of number theory, and Hofstadter includes lengthy digressions on programming, and loops of operations nested within others.  It inspired me to find a BBC BASIC emulator and write a little programme that finds prime numbers.  Here is what I came up with:
10 CLS
40 FOR N = 3 TO L
50    FOR D = 2 TO (N-1)
60      IF N/D=INT(N/D) THEN GOTO 100
70    NEXT D
80    PRINT N;
90    GOTO 110
100   PRINT ".";
110 NEXT N
120 END

This programme asks you for a number, and it will search for prime numbers up to and including the number you give.  If it finds a prime, it prints it, otherwise it just prints a dot.  I chose this method of output so that one has a visual representation of how primes are distributed throughout the natural numbers, and it is easy to spot Twin Primes.
Since we’re thinking about self-reference, I might as well make an observations about this post, which is that it will probably succeed in alienating everyone.  Those with no interest in maths and coding will likely think I am being terribly geeky.  Meanwhile, those who do take an interest in such things will scoff at the incredible simplicity of my coding ambitions.  Already one wag in the office has asked me why I don’t print all the discovered primes in an array…

The output from my programme.

8 Replies to “Prime Numbers and BASIC”

  1. In psychology also the ability of the brain/mind to represent itself is what gives rise to self-awareness, aka consciousness. You may also enjoy Metamagical Themas, if you haven’t already, which has some mind-boggling self-referential stuff.

  2. Thanks, I like the prog.
    have you tried a bingo program to pick out 12 unique numbers from 1 to 90 and then print them out in order (as a matrix complete with a box for each number. ie like on large square graph paper? Of course you need to check that your number generator will never – ever pick out the same numbers again!

  3. On line 40 add “step 2” to the end. This will skip all even numbers and speed up the search. (There arnt any even prime numbers, as they can all be decided by 2)

  4. In addition to BB’s step of 2 (so you skip testing for even numbers). Wouldn’t you only need to test the first half of the numbers… (e.g. if trying to see if 347 is a prime you only need to test up to 173. As any number higher than 1/2 the test value would not evenly divisible)?
    If using integer basic you can use the MOD function which should save one math test in line 60 and save a few cycles:
    10 CLS
    20 PRINT “LIMIT “;
    30 INPUT L
    40 FOR N=3 TO L STEP 2
    50 FOR D=2 TO (N/2)+1
    60 IF N MOD D=0 THEN GOTO 100
    70 NEXT D
    80 PRINT N;”.”;
    90 GOTO 110
    100 PRINT “..”;
    110 NEXT N
    120 END

  5. First 100 primes:
    1 FOR N = 2 TO 542
    2 FOR D = 2 TO (N-1)
    3 IF N/D = INT(N/D) THEN
    4 GOTO 8
    5 END IF
    6 NEXT D
    7 PRINT N;
    8 NEXT N
    Any idea to make it shorter?
    Thanks in advance

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.