Finding prime divisors with wheel factorization I am just starting to learn C++, and I wrote was the following implementation of the trial division algorithm to find the prime factors of a positive integer. I'm hoping the community here can suggest changes to both the algorithm and to the implementation. I barely know any language-specific features of C++, so I'm sure there is a lot of room for improvement.

In particular, I would like to be able to the following things:


Work with larger integers than what int allows.
Catch errors arising from command-line arguments that cannot be parsed as ints.
Remove the hard-coding of the wheel and the cases of the first primes 2, 3, and 5.
Improve general style/use more features of C++.




#include &lt;iostream&gt;

/*
 * Print out p as many times as it divides n.
 * Return the quotient of n by the highest power of p dividing n.
 */
int checkdivisor(int n, int p) {
  while (n % p == 0) {
    std::cout &lt;&lt; p &lt;&lt; std::endl;
    n /= p;
  }
  return n;
}

// Wheel for eliminating more composite numbers.
const int PERIOD = 7;
const int WHEEL235[PERIOD] = {4, 2, 4, 2, 4, 6, 2};

/*
 * Print the prime divisors of n.
 * The algorithm is trial division with 2-3-5 wheel factorization.
 */
void primedivisors(int n) {
  if (n &gt; 1) {
    // Check 2, 3, and 5 individually
    n = checkdivisor(n, 2);
    n = checkdivisor(n, 3);
    n = checkdivisor(n, 5);
    // Start at the next potential prime divisor, 7.
    int p = 7;
    int i = 0;
    while (n &gt; 1) {
      // If p^2 &gt; n, then n is the last remaining prime divisor.
      if (p * p &gt; n) {
        std::cout &lt;&lt; n &lt;&lt; std::endl;
        return;
      }
      // Check if p is a prime divisor.
      n = checkdivisor(n, p);
      // Increment p based on the wheel.
      p += WHEEL235[i++ % PERIOD];
    }
  }
}

/*
 * Parse command-line arguments as ints (if possible), and print their prime
 * factors.
 */
int main(int argc, char* argv[]) {
  for (int i = 1; i &lt; argc; i++) {
    primedivisors(std::stoi(argv[i]));
  }
}
Work with larger integers than what int allows

Here, you seem to be asking for templates, so that your code works with any integer (and actually, any type which properly acts like an integer). I will convert the checkdivisor function for you so that you can analyze it, then templating the rest of the code will be left as an exercice:

template&lt;typename Integer&gt;
Integer checkdivisor(Integer n, Integer p) {
  while (n % p == 0) {
    std::cout &lt;&lt; p &lt;&lt; std::endl;
    n /= p;
  }
  return n;
}


Actually, it should even work with any type for which the operations %, / and == have the desired semantics.

Catch errors arising from command-line arguments that cannot be parsed as ints

That one is easy if you look at the documentation of std::stoi: it says that std::stoi throws an std::invalid_argument exception if the string does not represent an integer and an std::out_of_range exception if the string to parse represents an integer too big for the type to hold. Knowing that, you can set up a simple try/catch to handle the errors:

int main(int argc, char* argv[]) {
  for (int i = 1; i &lt; argc; i++) {
    try {
      primedivisors(std::stoi(argv[i]));
    }
    catch (const std::invalid_argument&amp; err) {
      std::cerr &lt;&lt; "the input is not an integer\n";
    }
    catch (const std::out_of_range&amp; err) {
      std::cerr &lt;&lt; "the input is too big\n";
    }
  }
}