We discuss how much space is sufficient to decide whether a unary given number
n is a prime. We show that
O(log log n) space is sufficient for a deterministic
Turing machine, if it is equipped with an additional pebble movable along the input tape,
and also for an alternating machine, if the space restriction applies only to its
accepting computation subtrees. In other words, the language is a prime is in
pebble–DSPACE(log log n) and also in
accept–ASPACE(log log n). Moreover, if the given
n is composite, such machines are able to find a divisor of
n. Since O(log log n) space is too
small to write down a divisor, which might require
Ω(log n) bits, the witness divisor is indicated by the
input head position at the moment when the machine halts.