# Complexity of testing if a number is a primorial

For the $n$-th prime number $p_n$ the primorial $p_n\#$ is defined as the product of the first $n$ primes.

What is the complexity of testing if a given number $n$ is a primorial?
Is it related in some way to the FACTORING problem?
-

This is simpler than factoring. You can simply multiply all prime numbers up to the point where you (a) reach $p_n$ or (b) get a product which is larger than $p_n$. In the first case, you answer yes otherwise you answer no.
But in order to find the primes you must scan all the numbers and are you sure that this doesn't lead to an exponential number of steps (the input size is $\log n$ where $n$ is the number that must be tested)? –  Vor Jan 16 '13 at 9:32
But primorials grow in the order of $e^{O(n \log n)}$ meaning that you need logarithmically many primes to reach the needed product. –  Pål GD Jan 16 '13 at 9:35