Primality Testing in Manufactoria

Question

Background

Manufactoria is a game about programming. The player must use a form of two-dimensional programming language to complete tasks. If you've never heard of it, the easiest way to learn is to try out the first few levels of the game.

Challenge

Your challenge is to create a program which tests the primality of a number.

The input will be a series of N blue markers in the queue. If N is prime, then your program should accept it (move the robot to the finish). If N is composite, then your program should reject it (drop it on the floor somewhere).

Submission Options

Since this is a more complex challenge than the typical Manufactoria challenge, I have decided to allow more ways to submit your answers.

Vanilla

I have created a 13x13 custom level to build and test submissions. The custom testing level is as follows.

13x13 custom level

The game only allows 8 test cases on a custom level, but your creation should be theoretically able to handle any natural number N, limited only by the available memory. For informational purposes, the test cases provided in the custom level are as follows:

1 -> reject
2 -> accept
4 -> reject
5 -> accept
7 -> accept
9 -> reject
11-> accept
15-> reject

Expanded Grid

Some users may want more room than a 13x13 grid. Here is a link to an in-game 15x15 custom level, created by changing a number in the URL:

15x15 custom level

Sadly, larger custom levels don't work, as the additional cells are inaccessible.

The Manufactoria Esolang

There has been an adaption of Manufactoria into an ASCII-based language. If you want a different way to design/test your creation, or if you are unable to fit your final solution onto the game board, you can use this esolang. You can find information on this esolang here:

Manufactoria esolang

There are a few discrepancies between the esolang and the actual game. For example, conveyor crossings are handled differently. Try to avoid taking advantage of these discrepancies.

A Faster Way to Test

The game is very slow when it comes to programs which take several thousands of steps to complete. My proof-of-concept solution took 28042 steps to reject 15. Even at the 50x speedup in-game, that simply takes too long.

I found this very helpful website. Simply copy-paste the link to your answer, and you can test your answer with specific inputs. The 28042-step process took under a second.

One thing to note is that it will often say something like "incorrectly accepted" even if your machine worked properly. This is because the webpage only knows the test cases. For example, it would say that my solution "incorrectly accepted" the number 3, even though my machine was actually correct.

How to Win

The scoring criteria is the number of parts (cells occupied). This is code golf, so the submission with the fewest parts wins.

For those interested, my benchmark solution has 96 parts and fits on the 13x13 grid. Finding a better algorithm could lead to colossal improvements, since I know I used a sub-optimal algorithm.

Answer 1

53 parts - 11x11 grid

I just learned to play Manufactoria 2 days ago, so it is probably not very golf-optimized, but at least it solves the problem. It implements trial division of course, via repeated subtraction. All divisors from 2 to N-1 are checked. The time complexity should be O(N^3), I believe.

Solution Link

I was very disappointed to have to use a conveyor belt :)