Primality Testing in Manufactoria
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 :)