An algorithm given by Ambainis and Freivalds [1] constructs a quantum finite automaton (QFA) withO(logp) states recognizing the language L p = a i |i is divisible by p with probability 1 − ε, for any ε > 0 and arbitrary prime p. In [4] we gave examples showing that the algorithm is applicable also to quantum automata of very limited size. However, the Ambainis-Freivalds algoritm is tailored to constructing a measure-many QFA (defined by Kondacs and Watrous [2]), which cannot be implemented on existing quantum computers. In this paper we modify the algorithm to construct ameasure-once QFA of Moore and Crutchfield [3] and give examples of parameters for this automaton. We show for the language L p that a measure-once QFA can be twice as space efficient as measure-many QFA’s.