Search

jeudi 16 février 2017

Display all prime numbers

Context

A prime number is a number that allows only 2 distinct divisors: 1 and itself.
First prime numbers are 2, 3, 5, 7, 11 ...
Computing all prime numbers up to a limit can be implemented using a sieve, that works like this

  • Generate an array of all integers from 2 up to the limit
  • Go to the first non-null item in the array
    • This number N is prime
    • Then, reset array items every N cells starting from this one
Example: 2 is prime, and all multiple of 2 are removed, then 3 is a prime and all multiples of 3 are removed, including 6 that will be reset twice (once for 2, and once for 3), then 4 is null (reset by 2), so move to 5, ...

Initial state

  • Memory: empty
  • Cursor: first cell
  • Input: any

Process

  • First, define a 'comma' on first cell (code: 44), because we'll display comma-separated numbers, so it avoids building the comma everytime.
    • Note: this is equivalent to a constant value in other programming languages...
  • Then, generate all numbers from limit to 2, in decreasing order, in a 2-cells array, but this time it'll be [{value, 1}]  instead of [{1, value}] (code is a bit shorter)
    • Generate the limit (using '-', we'll have 255, the biggest possible value)
    • Set next cell to 1
    • While current value is not null
      • Copy 2 cells ahead
      • Set next cell to 1
      • Decrease copied value by 1, and stay on this value
    • Result will be an array from 255 to 0, let's just remove the extra cells at the end.
  • Finally, go to the first cell
    • If value is not null
      • Print the number
      • Print comma
      • Copy / move it twice: one for backup, one for counter
      • Iterate on all array cells
        • Move 2-cells block to the right
        • Decrease counter. If null
          • Reset copied cell
          • Reset counter to initial value (copy from backup)
      • Move whole array at its original position
    • Go to next cell

Code - try it

generate comma
>++++[-<+++++++++++>]
generate all numbers from max to 2
>-[[->+>+<<]>[-<+>]+>-]<-<-<

[
  go to current number
  -<
  [
    number is not null: prime
    copy twice and print
    [->>+>>+<<<<]
    >>>>[>>>>++++++++++<<<<[->+>>+>-[<-]<[->>+<<<<[->>>+<<<]>]<<]>+[-<+>]>>>[-]>[-<<<<+>>>>]<<<<]<[>++++++[<++++++++>-]<-.[-]<]
    print comma
    <<<<[<<]<.>>>[>>]
    copy counter
    >[->+>>+<<<]>[-<+>]<

    for each cell
    <<<[
      move
      -<[->>+<<]>>>+
      go to counter and decrease then check if null
      [>>]+<-[>-]>[-
        reset last copied cell
        <<[<<]>[-]>[>>]
        reset counter
        >>[-<+<<+>>>]<[->+<]
      ]
      process next cell
      <<<[<<]<<
    ]
    move back all cells
    >>>>[<[-<<+>>]<+>>->>]
    clear counters
    <[-]>>>[-]<<<<<
  ]
  process next number
  <
]

Final state

  • Memory: 44 0 0 0 (44 is code for comma)
  • Cursor: second cell
  • Input: unchanged
  • Output: all primes below 255, comma separated, with extra comma - note that extra comma can be removed by adding a Backspace character (code = 10). Simply add ++++++++++. at the end of the code.

1 commentaire:

  1. Thanks for sharing such a nice blog. Mobile number generator tool is an online tool to generate mobile number of any digits Mobile number generator

    RépondreSupprimer