Giter VIP home page Giter VIP logo

c-rho's Introduction

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

c-rho's People

Stargazers

 avatar  avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. 📊📈🎉

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.