Finding prime divisors with wheel factorization

Question

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

/*
 * 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 << p << 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 > 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 > 1) {
      // If p^2 > n, then n is the last remaining prime divisor.
      if (p * p > n) {
        std::cout << n << 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 < argc; i++) {
    primedivisors(std::stoi(argv[i]));
  }
}

Answer 1

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<typename Integer>
Integer checkdivisor(Integer n, Integer p) {
  while (n % p == 0) {
    std::cout << p << 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 < argc; i++) {
    try {
      primedivisors(std::stoi(argv[i]));
    }
    catch (const std::invalid_argument& err) {
      std::cerr << "the input is not an integer\n";
    }
    catch (const std::out_of_range& err) {
      std::cerr << "the input is too big\n";
    }
  }
}

Answer 2

For larger "integers" maybe use the gmp library - or write your own arbitrary precision arithmetic. Gmp also comes with functions for finding primes - but I suppose it is your goal to implement your own.

As code review I would strongly suggest you don't do so much inside the primedivisors function. I would split it up into a function to find the next prime, checkdivisors you already have separate. Having the output separate from the math would also make it more readable. In my opinion it would make sense to first generate the list of prime divisors and in a second step output it.

Obviously you will need your own function to construct the wheel - it should be pretty straightforward. You can also look at a professional implementation at primesieve