An algorithm given by Ambainis and Freivalds [1] constructs a quantum finite automaton (QFA) with O(logp) states recognizing the language L_p = aⁱ|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 a measure-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.