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

  • $\begingroup$ 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? $\endgroup$ – Rick Decker Aug 8 '13 at 12:35
  • $\begingroup$ @RickDecker It should fit into an int , i want to check only for small numbers .. maybe up to $10^4$. $\endgroup$ – sigmatau Aug 8 '13 at 12:37
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson Aug 8 '13 at 12:39
  • $\begingroup$ @GerryMyerson yes i programmed two functions for that purpose. Thanks for your feedback! $\endgroup$ – sigmatau Aug 8 '13 at 12:40
  • 1
    $\begingroup$ Your algorithm will fail for prime powers $p^n$, because $a_2=a_3$ but $a_1 \ne 0$. $\endgroup$ – 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.

  • $\begingroup$ How do you get those numbers? IMO $a_2=4$ and $a_3=7.$ $\endgroup$ – gammatester Aug 8 '13 at 13:29
  • $\begingroup$ @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>. $\endgroup$ – Rick Decker Aug 8 '13 at 13:38
  • $\begingroup$ 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! $\endgroup$ – sigmatau Aug 8 '13 at 13:39
  • $\begingroup$ 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. $\endgroup$ – Greebo Aug 8 '13 at 13:46
  • $\begingroup$ I'm a little uncertain how we would know, using only the primes "up to $\sqrt{n}$" as @Greebo suggests, that we have found n/p[i] to be a consecutive prime factor following the largest one p[i] in our list. We could of course check primality of all the integers strictly between p[i] and n/p[i], but likely it would make sense to include an extra prime, one just above $\sqrt{n}$, in the list. $\endgroup$ – hardmath Aug 8 '13 at 15:36

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.

  • $\begingroup$ Very cute, Dan. +1 $\endgroup$ – Rick Decker Aug 9 '13 at 14:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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