[Solved]: Time complexity of generating the first n primes and their product

Problem Detail: 

Suppose that I have a turing machine that receives as input the string $1^{n\times n}$ (unary input), what is the time complexity of writing $p_1,...,p_n$ on the output tape, where $p_i$ is the i-th prime number (written in binary)? And writing the first $n$ primes followed by their product (all written in binary)?

Asked By : user6638

Answered By : Ran G.

Since the input is of length $n^2$, it makes sense that the TM must read it at least once (to learn the value of $n$), and we have a trivial lower bound of $\Omega(n^2)$. It is my understanding that what you actually ask is "can we complete the task with $O(n^2)$ steps as well"?

You suggest using the Sieve of Eratosthenes to mark primes. This is a clever idea. Indeed, a possible TM can run over the input. Each time it finds a 1, it writes its index on the output tape ($p_i$), and go through the input tape, zeroing any multiply of $p_i$. Then it goes back to index $p_i$ and repeat.

In order to know the index, we can assume the TM maintains a counter on the output tape (which is being "pushed" every time the TM outputs a new prime).

Now let's analyze the running time.

1. reading the input - $n^2$
2. For any prime we find (and we have $n$ of those:)
   1. mark the input tape according to the Sieve of Eratosthenes: we need to go through approximately $O(n\log n)$ numbers due to the density of primes - $O(n\log n)$
   2. push the index and write the output - $O(\log n)$
   3. counting exactly $p^i$ steps between two indexes we zero - $O(n\log^2n)$
3. Multiplying all primes - $O(n^2\log^{1+\epsilon}n)$

so the naïve solution above takes $O(n^2) + n\times [ O(n\log n) + O(n\log^2 n)] + O(n^2\log^{1+\epsilon} n)= O(n^2\log^2n)$. In the above I assumed counting takes $O(n\log^2 n)$ since each step we need to subtract 1 from a $\log n$-long number, for every step in the sieve (which we bound to length $O(n\log n)$).

The time complexity of that algorithms is $O(n^2\log^2 n)$.

However, things can get better, as there are other ways of sieving. Assuming a multitape TM, the sieve of up to $k$ can be computed using $O(k/\log\log k)$ additions (thus, with $O(k\log k/\log\log k)$ bit-operations) by [1]. By setting $k=O(n\log n)$, we can compute the sieve with $O(n\log n)$ steps.

However, computing the multiplication of $n$ numbers (of length $\log n$) will take $n \times O(MUL_{\log n})$ where $MUL_k$ is the time to multiply two numbers of length $k$. According wikipedia, $MUL_k \approx O(n\log n )$ ^[2]. This step alone is $\Omega(n^2\log n)$ and I don't see much hope to get complexity of $O(n^2)$.

---

_{[1]: A. O. L. Atkin and D. J. Bernstein, "Prime sieves using binary quadratic forms" (free-access), Mathematics of Computation 73 (2004), pp. 1023–1030.
[2]: ignoring the practically constant term of $2^{\log^* n}$.}

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9330