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

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 !!

-
Are there any conditions on the input number $n$? Since you're writing a program, can you assert that $n$ will fit in an int or long, for instance? – Rick Decker Aug 8 '13 at 12:35
@RickDecker It should fit into an int , i want to check only for small numbers .. maybe up to $10^4$. – sigmatau Aug 8 '13 at 12:37
Your algorithm should work --- provided you figure out how to find the prime factors of $n$, and how to find the number of primes up to a given bound. – Gerry Myerson Aug 8 '13 at 12:39
@GerryMyerson yes i programmed two functions for that purpose. Thanks for your feedback! – sigmatau Aug 8 '13 at 12:40
Your algorithm will fail for prime powers $p^n$, because $a_2=a_3$ but $a_1 \ne 0$. – gammatester Aug 8 '13 at 12:42

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.

-
How do you get those numbers? IMO $a_2=4$ and $a_3=7.$ – gammatester Aug 8 '13 at 13:29
@gammatester. You're correct. I missed the "<" in (4) and miscounted as well. The answer has been fixed. As a result, both of our previous comments are now null references <grin>. – Rick Decker Aug 8 '13 at 13:38
I just edited the error since @gammatester pointed it out in the comments. I used a strict inequality in step (4) to fix it. But thanks for pointing it out! – sigmatau Aug 8 '13 at 13:39
You would only need the precomputed array to go up to $\sqrt{n}$, and if none of these divide $n$, $n$ is prime, so therefore also fullfills the requirements. – Greebo Aug 8 '13 at 13:46
@Greebo. Post in haste, repent at leisure. – Rick Decker Aug 8 '13 at 13:50

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.

-
Very cute, Dan. +1 – Rick Decker Aug 9 '13 at 14:09