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

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(nlog n)$ numbers due to the density of primes – $O(nlog n)$
   2. push the index and write the output – $O(log n)$
   3. counting exactly $p^i$ steps between two indexes we zero – $O(nlog^2n)$
3. Multiplying all primes – $O(n^2log^{1+epsilon}n)$

so the naïve solution above takes $O(n^2) + ntimes [ O(nlog n) + O(nlog^2 n)] + O(n^2log^{1+epsilon} n)= O(n^2log^2n)$. In the above I assumed counting takes $O(nlog^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(nlog n)$). The time complexity of that algorithms is $O(n^2log^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/loglog k)$ additions (thus, with $O(klog k/loglog k)$ bit-operations) by [1]. By setting $k=O(nlog n)$, we can compute the sieve with $O(nlog 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(nlog n )$ [2]. This step alone is $Omega(n^2log 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}$.