The prefix problem consists of computing all the products $x0x1\dots xj(j=0,\dots ,N-1)$, given a sequence $X=(x0,x1,\dots ,xN-1)$ of elements in a semigroup. In this paper we completely characterize the size-time complexity of computing prefixes with boolean networks, which are synchronized interconnections of boolean gates and one-bit storage devices. This complexity crucially depends upon a property of the underlying semigroup, which we call cycle-freedom (no cycle of length greater than one in the Cayley graph of the semigroup). Denoting by $S$ and $T$ size and computation time, respectively, we have $S=\Theta ((N/T)\log (N/T))$, for non-cycle-free semigroups, and $S=\Theta ((N/T)$, for cycle-free semigroups. In both cases, $T\in [\Omega (\backslash logN),O(N)]$.