Factor integers in C

Basic C99 factorization software.

This ~100 lines C software :

uses a Miller–Rabin primality test
uses a Pollard's rho algorithm

Example output

  358205873110913227 =    380003149 * 942639223    took 0.01s
  195482582293315223 =    242470939 * 806210357    took 0.0021s
  107179818338278057 =    139812461 * 766597037    took 0.0023s
   44636597321924407 =    182540669 * 244529603    took 0s
  747503348409771887 =    865588487 * 863578201    took 0.016s

// GCC 128-bit extension available output :
170141183460469231731687303715506697937 =
13602473 * 230287853 * 54315095311400476747373 took 0.137699s

2139508543525359760856377898747 = 18122728927937 * 118056643236947131 took 17.2946s
2080913777018885818418638213057 = 283954641807703 * 7328331608778919 took 40.8842s

factor(n, array)

parameter 1: positive_number N
parameter 2: positive_number* array

Fill the second parameter array with the prime factors of N.

// 64-bit source code is here.

#include <stdio.h>

int main(void) {
    // allocate memory for 64 factors.
    positive_number *array = calloc(64, sizeof(positive_number));

    positive_number n = 7806418495977353572 ;

    size_t n_factors = factor(n, array) - array ;
    printf("There are %zu factors of %llu : \n", n_factors, n);
    for(int i = 0; array[i]; ++i)
        printf("- %llu\n", array[i]);
    free(array);
}

So you displayed the factors of n :

There are 4 factors of 7806418495977353572 : 
- 2
- 2
- 120317621
- 16220438933

Compilation

The software should be executable on many platforms like Windows, Debian, Ubuntu, Linux, ...
You can rename main-64-bits.c or main-128-bits.c to primes.c then compile + execute :

gcc -O3 -std=c99 -Wall -pedantic primes.c ;
./a.out ;

You can normally try it online with DigitalOcean 128-bits, Thank You.

Shortest link to this page : bit.ly/C-RHO

michel-leonard/C-RHO

Factor integers in C

Example output

factor(n, array)

Compilation