.         110

.       x  11

.      ------

.         110

.      + 110

.      ------

.       10010

.                             a[2]      a[1]      a[0]

.              x                        b[1]      b[0]

.            -----------------------------------------

.                        a[2]*b[0] a[1]*b[0] a[0]*b[0]

.      +       a[2]*b[1] a[1]*b[1] a[0]*b[1]

.  ---------------------------------------------------

.        r[4]       r[3]      r[2]      r[1]      r[0]

/********************

 *  Factorisation

 *     Algorithme naïf

 */



#include <stdio.h>





void init(int n) {

	int j = 2;

	int i = n;

	while (i != 1) {

		

		if ((i % j) == 0) {

			i = i/j;

			printf("%i ",j);

		} else

			j++;

		

	}

	printf("\\n");

}





int main(int argc, char **argv) {

	int i;

	for (i=1; i<argc;i++) {

		printf("factorisatin de %sn",*(argv+i));

		init(atoi(*(argv+i)));

	}

	return 0;

}

TboWan@Obelix:~/programmes$ time fac_naif 2147483647

factorisatin de 2147483647

2147483647



real    1m5.618s

user    1m4.810s

sys     0m0.030s

TboWan@Obelix:~/programmes$ time factorise 2147483647

factorisatin de 2147483647

( 2147483647 , 1 )

( 1 , 2147483647 )



real    0m0.058s

user    0m0.050s

sys     0m0.000s

[n-0-x@localhost C]$ ./fdn.o time factorise 2147483647

2 2 2 2 2 2 (... [ c'est vraiment très long, ça prend toutes les lignes de mon terminal]) 2 2 2 22 2

[3]+  Stopped                 ./fdn.o time factorise 2147483647

[n-0-x@localhost C]$

/********************

 *  Factorisation

 *     Algorithme naïf 2

 */



#include <stdio.h>



void init(int n) {

  int i;



  while (n%2==0) {printf("2 ");n=n/2;}



  for(i=3;i*i<=n;i+=2)

    if ((n % i) == 0) {

      n = n/i;

      printf("%i ",i);

    }

  printf("%i \n",n);

}



int main(int argc, char **argv) {

  int i;

  

  for (i=1; i<argc;i++) {

    printf("factorisation de %s\n",*(argv+i));

    init(atoi(*(argv+i)));

  }

  return 0;

}

cas = a[0] - '0' + 2*(b[0]-'0') + 4*( (som + (nombre[rang] - '0')) % 2);



en fait que fait a[0] - '0' ?? ca ne soustrait pas 2 string ?

si cela fonctionne keske ca donne comme resultat ? 

#include <stdio.h>

#include <gmp.h>



main(void)

{

   unsigned long int exp;

   mpz_t i,nb_bits,z,nombre,temp;

   mpz_init(i);

   mpz_init(nombre);

   mpz_init(z);

   mpz_init(nb_bits);

   mpz_init(temp);

   FILE *fichier;



   mpz_set_ui(nombre,1);

fflush(stdout);



   fichier=fopen("nb_premier.txt","a");         //fichier de sauvegarde



   while(1)

   {

      mpz_set_ui(nb_bits,mpz_sizeinbase(nombre,2));   //on récupère le NB de bits

      mpz_set_ui(z,1);

      mpz_set_ui(i,0);

      while(mpz_cmp(i,nb_bits)<0)         //tant qu'on a pas testé tous les bits

      {

         mpz_mul(z,z,z);

         mpz_mod(z,z,nombre);

         mpz_sub(temp,nb_bits,i);      //

         exp=mpz_get_ui(temp)-1;         //on teste si le bit

         mpz_ui_pow_ui(temp,2,exp);      //courant est à 1

         mpz_and(temp,nombre,temp);      //

         if(mpz_cmp_ui(temp,0)!=0)      //si il est à 1 alors

         {

            mpz_mod(z,z,nombre);

            mpz_add(z,z,z);

         }

         mpz_add_ui(i,i,1);         //incrémentation du compteur de boucle

      }

      if(mpz_cmp_ui(z,2)==0)            //si le nb est premier, on le sauvegarde

      {

         mpz_out_str(fichier,10,nombre);

         fprintf(fichier,"\n");

      }

      mpz_add_ui(nombre,nombre,2);         //on teste le nombre suivant

   }

} 

NOMBRE -> nombre à tester

I -> compteur de boucle

NB_BITS -> nombre de bits de NOMBRE

Z -> variable permettant de définir si NOMBRE est premier ou non



pour NOMBRE variant de 1 à l'infini

   1 -> Z

   nombre de bits de NOMBRE -> NB_BITS

   pour I variant de NB_BITS-1 à 0

      ((Z * Z) % NOMBRE) -> Z

      si (NOMBRE && 2^I) = 1 alors

         ((Z + Z) % NOMBRE) -> Z

      fin si

   fin pour

   si (Z = 2) alors

      sauvegarder NOMBRE

   fin si

   NOMBRE + 2 -> NOMBRE

fin pour

dim tableau(2 to 10001) as short 'parce qu'on peut pas faire plus grand



for i = 2 to 10001

   tableau(i) = 1

next



dim i,j as integer

i=2



REM au début de chaque boucle, i est premier

while i<10001

   j=i+i

   REM on supprime les multiples de i

   while j<10001

      tableau(j) = 0

      j = j+i

   wend

   i = i+1

   REM on parcour jusqu'au prochain premier

   while i<10001 and tableau(i) = 0

      i = i+1

   wend

wend



for i=2 to 10001

   if tableau(i) = 1 then

      print i ; " est premier"

   end if

next

/* factor -- print prime factors of n.

   Copyright (C) 86, 1995-2002 Free Software Foundation, Inc.



   This program is free software; you can redistribute it and/or modify

   it under the terms of the GNU General Public License as published by

   the Free Software Foundation; either version 2, or (at your option)

   any later version.



   This program is distributed in the hope that it will be useful,

   but WITHOUT ANY WARRANTY; without even the implied warranty of

   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the

   GNU General Public License for more details.



   You should have received a copy of the GNU General Public License

   along with this program; if not, write to the Free Software Foundation,

   Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA.  */



/* Written by Paul Rubin <phr@ocf.berkeley.edu>.

   Adapted for GNU, fixed to factor UINT_MAX by Jim Meyering.  */



#include <config.h>

#include <stdio.h>

#include <sys/types.h>



#include <assert.h>

#define NDEBUG 1



#include "system.h"

#include "closeout.h"

#include "error.h"

#include "inttostr.h"

#include "long-options.h"

#include "readtokens.h"

#include "xstrtol.h"



/* The official name of this program (e.g., no `g' prefix).  */

#define PROGRAM_NAME "factor"



#define AUTHORS "Paul Rubin"



/* Token delimiters when reading from a file.  */

#define DELIM "nt "



/* FIXME: if this program is ever modified to factor integers larger

   than 2^128, this constant (and the algorithm  will have to change.  */

#define MAX_N_FACTORS 128



/* The trial divisor increment wheel.  Use it to skip over divisors that

   are composites of 2, 3, 5, 7, or 11.  The part from WHEEL_START up to

   WHEEL_END is reused periodically, while the "lead in" is used to test

   for those primes and to jump onto the wheel.  For more information, see

   http://www.utm.edu/research/primes/glossary/WheelFactorization.html  */



#include "wheel-size.h"  /* For the definition of WHEEL_SIZE.  */

static const unsigned int wheel_tab[] =

  {

#include "wheel.h"

  };



#define WHEEL_START (wheel_tab + WHEEL_SIZE)

#define WHEEL_END (wheel_tab + (sizeof wheel_tab / sizeof wheel_tab[0]))



/* The name this program was run with. */

char *program_name;



void

usage (int status)

{

  if (status != 0)

    fprintf (stderr, _("Try `%s --help' for more information.n"),

	     program_name);

  else

    {

      printf (_("

Usage: %s [NUMBER]...n

  or:  %s OPTIONn

"),

	      program_name, program_name);

      fputs (_("

Print the prime factors of each NUMBER.n

n

"), stdout);

      fputs (HELP_OPTION_DESCRIPTION, stdout);

      fputs (VERSION_OPTION_DESCRIPTION, stdout);

      fputs (_("

n

  Print the prime factors of all specified integer NUMBERs.  If no argumentsn

  are specified on the command line, they are read from standard input.n

"), stdout);

      printf (_("nReport bugs to <%s>.n"), PACKAGE_BUGREPORT);

    }

  exit (status);

}



/* FIXME: comment */



static int

factor (uintmax_t n0, int max_n_factors, uintmax_t *factors)

{

  register uintmax_t n = n0, d, q;

  int n_factors = 0;

  unsigned int const *w = wheel_tab;



  if (n < 1)

    return n_factors;



  /* The exit condition in the following loop is correct because

     any time it is tested one of these 3 conditions holds:

      (1) d divides n

      (2) n is prime

      (3) n is composite but has no factors less than d.

     If (1) or (2) obviously the right thing happens.

     If (3), then since n is composite it is >= d^2. */



  d = 2;

  do

    {

      q = n / d;

      while (n == q * d)

	{

	  assert (n_factors < max_n_factors);

	  factors[n_factors++] = d;

	  n = q;

	  q = n / d;

	}

      d += *(w++);

      if (w == WHEEL_END)

	w = WHEEL_START;

    }

  while (d <= q);



  if (n != 1 || n0 == 1)

    {

      assert (n_factors < max_n_factors);

      factors[n_factors++] = n;

    }



  return n_factors;

}



/* FIXME: comment */



static int

print_factors (const char *s)

{

  uintmax_t factors[MAX_N_FACTORS];

  uintmax_t n;

  int n_factors;

  int i;

  char buf[INT_BUFSIZE_BOUND (uintmax_t)];



  if (xstrtoumax (s, NULL, 10, &n, "") != LONGINT_OK)

    {

      error (0, 0, _("`%s' is not a valid positive integer"), s);

      return 1;

    }

  n_factors = factor (n, MAX_N_FACTORS, factors);

  printf ("%s:", umaxtostr (n, buf));

  for (i = 0; i < n_factors; i++)

    printf (" %s", umaxtostr (factors[i], buf));

  putchar ('n');

  return 0;

}



static int

do_stdin (void)

{

  int fail = 0;

  token_buffer tokenbuffer;



  init_tokenbuffer (&tokenbuffer);



  for (;;)

    {

      long int token_length;



      token_length = readtoken (stdin, DELIM, sizeof (DELIM) - 1,

				&tokenbuffer);

      if (token_length < 0)

	break;

      fail |= print_factors (tokenbuffer.buffer);

    }

  free (tokenbuffer.buffer);



  return fail;

}



int

main (int argc, char **argv)

{

  int fail;



  program_name = argv[0];

  setlocale (LC_ALL, "");

  bindtextdomain (PACKAGE, LOCALEDIR);

  textdomain (PACKAGE);



  atexit (close_stdout);



  parse_long_options (argc, argv, PROGRAM_NAME, GNU_PACKAGE, VERSION,

		      AUTHORS, usage);

  /* The above handles --help and --version.

     Since there is no other invocation of getopt, handle `--' here.  */

  if (argc > 1 && STREQ (argv[1], "--"))

    {

      --argc;

      ++argv;

    }



  fail = 0;

  if (argc == 1)

    fail = do_stdin ();

  else

    {

      int i;

      for (i = 1; i < argc; i++)

	fail |= print_factors (argv[i]);

    }

  if (fail)

    usage (EXIT_FAILURE);



  exit (fail);

}