Algorithm to determine if a number is a product of consecutive primes

Question

I want to implement a program in C++ with which I can see if a number $n$ has a prime factorization of only consecutive primes.

For example $30=2\cdot 3 \cdot 5$ is such a number, while $21=3 \cdot 7$ isn't because $5$ is missing. Repeated prime factors are allowed so $60=2^2 \cdot 3 \cdot 5$ would have the desired property. Before getting my hands on the keyboard I was figuring out how a possible algorithm might look.

Here is what i have so far:

(1) Find the number of prime factors of $n$, call this number $a_1$

(2) Find the maximum of all prime factors of $n$, call it $M$

(3) Find the minimum of all prime factors of $n$, call it $m$

(4) Find the number of primes $< m$ call it $a_2$

(5) Find the number of primes $\leq M$ call it $a_3$

(6) If $a_1=a_3-a_2$ then $n$ has the property that we are looking for.

I have really limited knowledge in programming so the above algorithm would be one (maybe the only) way I am able to implement a program based on my knowledge.

my question : Can I achieve my goal by implementing the above algorithm or is there a serious mistake I overlooked? Thanks in advance !!

Answer 1

Since you stated that $n$ is fairly small, it would be efficient to precompute an array, $\mathtt{p[i]}$, of the primes, in order, less than or equal to the largest value you ever expect the input to be.* Then, starting at the smallest prime, $\mathtt{p[0]}$, see if $\mathtt{p[i]}$ divides $n$. If it doesn't divide $n$, increment $i$ and continue. If it does divide $n$, check whether it divides $\mathtt{n/p[i]}$. If it does, quit, since you don't want repeated factors of the same prime. Otherwise check whether $\mathtt{p[i+1]}$ divides $n$. If so, keep going and if not, again quit. Rinse and repeat.

*Edit. As Greebo pointed out, your list of primes need only go up to the largest prime $\le\sqrt{n}$. For inputs less than a million, you'll only need 168 primes.

Answer 2

Here is another method that doesn't require any precomputation:

$n$ has between $1$ and $\log_2(n)$ prime factors so let's consider each case separately. First, test if $n$ is prime, in which case return TRUE. Now, if $n$ has exactly two consecutive prime factors they are precisely the greatest prime less than or equal to $\sqrt{n}$ and the smallest prime greater than or equal to $\sqrt{n}$. Going on in this fashion, if $n$ has exactly $k$ prime factors which are consecutive then at least one of them is less than or equal to $n^{\frac{1}{k}}$ and at least one of them is greater than or equal to $n^{\frac{1}{k}}$, so they can be identified by testing for primes in the window around $n^{\frac{1}{k}}$. Now we just do this for every k between $1$ and $\lfloor \log_2{n} \rfloor$.

This has an average-case running time which is polynomial in $\log{n}$ so for large random $n$ it is probably faster than first factoring $n$ using a general-purpose method and checking if they are consecutive.