  Quantum algorithms are at the heart of the ongoing efforts to use quantum
mechanics to solve computational problems unsolvable on ordinary classical
computers. Their common feature is the use of genuine quantum properties such
as entanglement and superposition of states. Among the known quantum
algorithms, a special role is played by the Shor algorithm, i.e. a
polynomial-time quantum algorithm for integer factorization, with far reaching
potential applications in several fields, such as cryptography. Here we present
a different algorithm for integer factorization based on another genuine
quantum property: quantum measurement. In this new scheme, the factorization of
the integer $N$ is achieved in a number of steps equal to the number $k$ of its
prime factors, -- e.g., if $N$ is the product of two primes, two quantum
measurements are enough, regardless of the number of digits $n$ of the number
$N$. Since $k$ is the lower bound to the number of operations one can do to
factorize a general integer, one sees that a quantum mechanical setup can
saturate such a bound.
