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
int
s. - 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]));
}
}
7081
is prime because it missesn=73
. \$\endgroup\$const int WHEEL235[PERIOD] = {4, 2, 4, 2, 4, 6, 2};
should include another 6 at the end \$\endgroup\$