gmp

From the documentation:

GNU MP is a library for arbitrary precision arithmetic, operating on signed integers, rational numbers, and floating point numbers. It has a rich set of functions, and the functions have a regular interface.

So, anyway, it does bignums. I felt like learning the API to this library, so I wrote this fun little program for factoring arbitrary integers today:

#include <stdio.h>
#include <gmp.h>


void factors(mpz_t);
void firstfactor(mpz_t, mpz_t, mpz_t);


int main(int argc, char **argv)
{
  mpz_t x;
  mpz_init(x);
  while(!feof(stdin)) {
    mpz_inp_str(x, stdin, 10);
    factors(x);
  }

  return 0;
}

void firstfactor(mpz_t x, mpz_t left, mpz_t fact)
{
  mpz_t n, quot, rem;

  mpz_init(quot);
  mpz_init(rem);
  mpz_init_set_si(n, 2);

  while(mpz_cmp(n, x) < 0) {
    mpz_tdiv_qr(quot, rem, x, n);
    if(mpz_cmp_si(rem, 0)==0) {
      mpz_set(left, quot);
      mpz_set(fact, n);
      return;
    }
    mpz_add_ui(n, n, 1);
  }
  mpz_set_si(left, -1);
  mpz_set(fact, x);
  return;
}

void factors(mpz_t x)
{
  mpz_t fact, left;

  mpz_init(fact);
  mpz_init(left);

  while(1){
    firstfactor(x, left, fact);
    mpz_out_str(stdout, 10, fact);
    printf(" ");
    if(mpz_cmp_si(left, -1)==0)
      break;
    mpz_set(x, left);
  }
  printf("\n");
  return;
}