Integer factoring in C using GMP for numbers This code performs integer factoring using the GMP library, and can also use OpenMP for parallel computation.

I compile it using: gcc -lgmp -fopenmp and whatever optimization flags I wish to try.

#include &lt;stdio.h&gt;
#include &lt;gmp.h&gt;

void next_prime(MP_INT *x) {
    MP_INT r;
    mpz_init(&amp;r);
    if (!mpz_probab_prime_p(x, 128u)) {
        mpz_mod_ui(&amp;r, x, 2ul);
        if (mpz_cmp_ui(&amp;r, 0ul) == 0)
            mpz_add_ui(x, x, 1ul);
        else
            mpz_add_ui(x, x, 2ul);
        while (!mpz_probab_prime_p(x, 128u)) {
            mpz_add_ui(x, x, 2ul);
        }
    }
    mpz_clear(&amp;r);
}

void prev_prime(MP_INT *x) {
    MP_INT r;
    mpz_init(&amp;r);
    if (!mpz_probab_prime_p(x, 128u)) {
        mpz_mod_ui(&amp;r, x, 2ul);
        if (mpz_cmp_ui(&amp;r, 0ul) == 0)
            mpz_sub_ui(x, x, 1ul);
        else
            mpz_sub_ui(x, x, 2ul);
        while (!mpz_probab_prime_p(x, 128u)) {
            mpz_sub_ui(x, x, 2ul);
        }
    }
    mpz_clear(&amp;r);
}

unsigned long mp_log(MP_INT *x, MP_INT *base) {
    MP_INT r;
    mpz_init(&amp;r);
    unsigned long lg = 0;
    mpz_set(&amp;r, x);
    if (base != NULL) {
        while (mpz_cmp_ui(&amp;r, 0ul) != 0) {
            mpz_div(&amp;r, &amp;r, base);
            lg += 1;
        }
    }
    else {
        while (mpz_cmp_ui(&amp;r, 0ul) != 0) {
            mpz_div_ui(&amp;r, &amp;r, 2ul);
            lg += 1;
        }
    }
    mpz_clear(&amp;r);
    return lg;
}

void factor(MP_INT *x, MP_INT *n, MP_INT *base) {
    /* Initialize variables. */
    MP_INT s;
    MP_INT r;
    mpz_init(&amp;s);
    mpz_init(&amp;r);
    /* Compute stuff. */
    mpz_set(x, n);
    if (mpz_probab_prime_p(n, 128u)) {
        goto end;
    }
    mpz_set(&amp;s, base);
    mpz_mod(&amp;r, n, &amp;s);
    if (mpz_cmp_ui(&amp;r, 0ul) == 0) {
        mpz_set(x, &amp;s);
        goto end;
    }
    unsigned long k = mp_log(n, base);
    unsigned long a = mp_log(n, NULL);
    if (mpz_cmp(x, n) == 0) {
        /* Try different powers of n. */
        MP_INT p;
        mpz_init(&amp;p);
        mpz_pow_ui(&amp;p, &amp;s, k);
        unsigned long i = 1ul;
        while (mpz_cmp(x, n) == 0) {
            #pragma omp parallel for
            for (unsigned long j = i; j &lt; i + 2*a*a; ++j) {
                if (mpz_cmp(x, n) == 0) {
                    MP_INT g;
                    mpz_init(&amp;g);
                    mpz_powm_ui(&amp;g, n, j, &amp;p);
                    mpz_gcd(&amp;g, &amp;g, n);
                    if (mpz_cmp_ui(&amp;g, 1ul) != 0 &amp;&amp; mpz_cmp(&amp;g, n) != 0) {
                        mpz_set(x, &amp;g);
                    }
                    mpz_clear(&amp;g);
                }
            }
            i += 2*a*a;
        }
        mpz_clear(&amp;p);
    }
    /* Clear variables. */
    end:
    mpz_clear(&amp;s);
    mpz_clear(&amp;r);
}

int main() {
    char str [65536];
    char bas [65536];
    while (fscanf(stdin, "%s %s", str, bas) != EOF) {
        MP_INT n;
        MP_INT base;
        mpz_init(&amp;n);
        mpz_init(&amp;base);
        mpz_set_str(&amp;n, str, 10u);
        mpz_set_str(&amp;base, bas, 10u);
        mpz_out_str(stdout, 10u, &amp;n);
        int p = mpz_probab_prime_p(&amp;n, 128u);
        printf(" %d ", p);
        mpz_out_str(stdout, 10u, &amp;base);
        printf("\n");
        while (!p) {
            MP_INT x;
            mpz_init(&amp;x);
            factor(&amp;x, &amp;n, &amp;base);
            mpz_out_str(stdout, 10u, &amp;x);
            printf(" ");
            mpz_div(&amp;n, &amp;n, &amp;x);
            p = mpz_probab_prime_p(&amp;n, 128u);
            mpz_clear(&amp;x);
        }
        mpz_out_str(stdout, 10u, &amp;n);
        printf("\n");
        mpz_clear(&amp;n);
        mpz_clear(&amp;base);
    }
    return 0;
}
You can improve the readability of your code, your indentation is great but you have magic numbers and the variable names aren't very clear. You probably wouldn't need comments if your variable names were clear and you had symbolic constants rather than numbers.

Magic Numbers:

You have a lot of raw numbers : 65536, 10u, 128u, 1ul, 2ul ...

For example you can have a symbolic constant CHARACTER_BUFFER_SIZE for 65536. Using the gcc compiler you would write your constant as 

#define CHARACTER_BUFFER_SIZE 65536 


When compiling with g++ you would use

static const CHARACTER_BUFFER_SIZE = 65536;


this would change the first 2 lines in main to

    char str[CHARACTER_BUFFER_SIZE];
    char bas[CHARACTER_BUFFER_SIZE];


If you use this number often, it makes it easier to change the value by just changing it where you define the constant. It also makes the code easier to read. The standard for symbolic constants in C and C++ is all caps with '_' between words.

Function Names:
Underscore in function names is a lot less common than it used to be, Camel Case is more common

next_prime =&gt; nextPrime
prev_prime =&gt; prevPrime


Variable Names:

The base variable name is almost understandable, but what kind of base, does it provide a starting point for the function, or is it a numeric base like Octal, Hex or Decimal?

It's really not clear from the code what x is.

In main() what are the variables str (almost obvious), bas, n, p, base?

Future Flexibility:

You main could be a little more flexible, currently you can only redirect input and a output, you could use command switches in your to select input and output files as well. In main it is possible to add a couple of FILE * variable to make it a little more general

    FILE *inputFile = stdin;
    FILE *outputFile = stdout;

    while(fscanf(inputFile, "%s %s", str, bas) != EOF) {
        ...
        mpz_out_str(outputFile, 10u, &amp;base);