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.
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