Can the prime-counting function and product of consecutive primes be calculated in polynomial time?

Question

In two algorithms I've been working with, I use the two functions:

1. pi(n):=number of primes <= n, and
2. R(n):=r, where prod(p_i,i=1,r)<=n but n < prod(p_i,i=1,r+1) where p_i is the i-th prime.

Basically pi(n) is the famous prime-counting function, and R(n) just calculates the product of consecutive primes until you reach the bound n and returns the amount of primes used, so for example:

R(12)=2 because 2*3<=12 but 2*3*5>12 and for example

R(100)=3 because 2*3*5<=100 but 2*3*5*7>100.

With my Professor we have been talking about the running time of calculating these functions. I know that the pi(n) that it approximates x/ln(x) over time, but I have my doubts about some stuff:

1. Can R(n) be calculated in polynomial time? From my point of view, by using dynamic programming we can calculate the products 2*3*5*...*p_i by knowing 2*3*5*...*p_(i-1), so the problem reduces to get the next prime, which as far as I know it can be calculated in polynomial time (PRIMES is in P).
2. Also because we know that we can determine if a number is prime in polynomial time, shouldn't that mean that pi(n) can be calculated in polynomial time? (Also using dynamic programming can be helpful).

If anyone can help me to clarify these questions or point me on the right direction, I would really appreciate it! Thank you!

Answer 1

For any n, you can easily determine if it's prime in O(n^(1/2)) time (check for divisibility by 2,3,4...,sqrt(n)), so you could just iterate over n and keep a counter as you go. If you store your primes in a list you could even speed it up checking whether each number is prime (check for divisibility by 2,3,5...,closest prime to sqrt(n)). So this algorithm for finding pi(n) should be O(n^(3/2)).

So let's say you run that algorithm and store the primes in a list. Then for R(n), you could just iterate through them to get their cumulative product, and return once you exceed n. I'm not sure what the time complexity of this would be, but it's going to be small. Probably something along the lines of O(log(n)), certainly something faster than O(n). Put both of those together and you should get something faster than O(n^(5/2)).