Tell me more ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.
up vote 1 down vote favorite

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?
share|improve this question

1 Answer

up vote 4 down vote accepted

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.

The reason it is simpler is that the prime factorization is trivial, whereas in the FACTORING problem, you don't know how many of each prime number you need.

share|improve this answer
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 at 9:32
1  
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 at 9:35

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.