We discuss how much space is sufficient to decide whether a unary given numbern is a prime. We show thatO(log log n) space is sufficient for a deterministicTuring 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 itsaccepting computation subtrees. In other words, the language is a prime is inpebble–DSPACE(log log n) and also inaccept–ASPACE(log log n). Moreover, if the givenn is composite, such machines are able to find a divisor ofn. Since O(log log n) space is toosmall to write down a divisor, which might requireΩ(log n) bits, the witness divisor is indicated by theinput head position at the moment when the machine halts.
