Forum de mathématiques - Bibm@th.net

Bonjour,

Merci de tes réponses mais je crois que j'exprime mal mon problème.
Prenons l'article de Wikipedia par exemple :http://fr.wikipedia.org/wiki/Crible_quadratique#cite_note-0
Il parle du crible quadratique qui est plus performant (donc plus rapide) que le crible généralisé.
Puis il donne une vielle formule des familles extrêmement intéressante mais que je ne comprends pas et que je ne veux même pas essayer de comprendre tellement je suis sûr de perdre mon temps!

L[tex]O\left(e^\sqrt{\log n \log\log n}\right)=L_n\left[1/2,1\right][/tex]

avec la notation O de Landau et la notation L (en)."

Damned : le copier/coller de la fonction (du Latex peut-être?) ne fonctionne pas!

Bref des exemples concrêts m'auraient fait un bien fou, du style pour n=123456789 le crible quadratique prend
7 secondes tandis que le crible quadratique n'en prend qu'une.

Sur cette base j'aurais pu calculer le facteur d'accélération qui ici aurait été de 7.
Or le second algorithme dont je parle dans mon premier post n'a un facteur d'accélération que de 2. Et tu as raison d'en parler, de 2 que pour les petits nombres (inférieurs à 64 bits). Mais, et là j'en suis certain, qui est de plus en plus performant au fur et à mesure que la taille des chiffres grandit (mais là il faut que je le prouve via l'informatique).

Je me suis mis au C pour vérifier mon algorithme (qui a la base est une relation mathématique). Si tu me dis :
1) qu'un facteur 2 est ridicule : alors je stoppe tout.
2) que ce facteur 2 est exploitable seulement s'il augmente avec la taille des chiffres : alors s'il le faut je me mette au Python qui comme j'ai cru le comprendre dans tes explications permet de travailler sur des chiffres de plusieurs milliers de chiffres. J'exposerais alors le résultat dans un blog.

Voilà je pense clairement exposé mon dilemme.

Bonjour,

Merci de ta réponse et joyeux Noël aussi!
Comme je ne sais pas coder en Python je choisis aussi ta première proposition.

Voici ce que j'appelle l'algorithme de référence.

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int main()
{
double duration;
clock_t start, end;
__int64 entier;
__int64 diviseur;
__int64 racine;
__int64 reste;

start = clock();

for(entier=1001;entier<10000001;entier+=2)
// La première boucle sert à "faire du volume" pour obtenir des temps
{

  racine = sqrt(entier) + 2;
  diviseur = 3;
  while (diviseur < racine)
  // La deuxième boucle est le réel programme de factorisation
  {
   reste = entier % diviseur;
   if (reste == 0)
   {
    //printf("le nombre %I64u est divisble par %I64u\n", entier, diviseur);
    break;
   }
   diviseur += 2;
  }
}
end = clock();
duration = ((double)(end - start)) / CLOCKS_PER_SEC;
printf("%f sec\n", duration);
return 0;
}

Bien évidemment ,étant amateur aussi en C, ce code est aussi perfectible quant à son écriture. Mais l'algorithme en lui même est celui qui est utilisé dans la plus simple expression de factorisation de nombre.
Attention : il ne sert qu'à trouver le plus petit diviseur d'un nombre.

Sur mon vieux coucou (un pentium3) pour 1001<entier<10000001 j'obtiens 92,773 secondes.