Algorythme d'euclide pour les nombres premiers

Soyez le premier à donner votre avis sur cette source.

Snippet vu 3 981 fois - Téléchargée 26 fois

Contenu du snippet

Ce code vous permet "theoriquement" de trouver tous les nombres premier entre 1 et un nombre que vous allez specifiez...
Donc pour avoir tous les nombres premiers entre 1 et 300 tapez

/premgen 300 et le code va plaser tous les nombres dans un fichier texte.

Malheureusement notre tres cher mirc plante si on lui demande trop de nombre premier... mais regardez le code avant :)

Source / Exemple :


alias premgen {
  ;fonctione sur toutes les versions mais est lent
  write -c nombre.txt 2 $+ $crlf $+ 3 $+ $crlf $+ 5 $+ $crlf $+ 7
  set %i 3
  while ( %i <= $1 ) { 
    set %j 1
    set %itr 1
    while (%j <= $lines(nombre.txt) ) {
      if ( $calc(%i / $read(nombre.txt,%j)) != $int($calc(%i / $read(nombre.txt,%j))) ) { inc %itr  }
      else { set %j $lines(nombre.txt) }
      inc %j
    }
    if ( $calc(%j - 1) = %itr  ) { write nombre.txt %i }
    inc %i 2
  }
  run nombre.txt
}

alias premgen2 {
  ;code infiniment plus rapide merci a SornDrixer
  if ( $version < 6.12 ) { echo -a ce code ne fonctione que sous version 6.12 | halt  }
  .fopen -on nombre nombre.txt
  .fwrite -n nombre 2 $+ $crlf $+ 3 $+ $crlf $+ 5 $+ $crlf $+ 7
  set %line 4
  set %i 3
  while ( %i <= $1 ) { 
    set %j 1
    set %itr 1
    while (%j <= %line ) {
      .fseek -l nombre %j
      set %fread $fread(nombre)
      if ( $calc(%i / %fread) != $int($calc(%i / %fread)) ) { inc %itr  }
      else { set %j %line }
      inc %j
    }
    if ( %j = %itr  ) { .fwrite -n nombre %i | inc %line }
    inc %i 2
  }
  .fclose nombre
  run nombre.txt
}

Conclusion :


Donc comme je disait ya un petit probleme, si vous demandez /premgen 2347 il y a de forte chance que ça plante donc eviter tous les chiffres superieurs a 2400

Adapté a d'autre langage le meme algorythme est plus interessant en turbo pascal on peut avoir tous les nombre premiers jusqu'a 10 000 rapidement

il a un autre defaut c'est un algorythme a "temps exponentiel" en gros c un escargot l'ideal est un algo a "temps polynomial" ( avis aux amateurs )

sinon c'est une source pas tres utiles c'est juse pour montrer qu'un pti logiciel pas adapté aux maths peut faire des choses sympa

Hééééé voila apres la remarque de SornDrixer une nouvelle fonction est sortie avec le File Handling elle n'est valable que sous version 6.12

J'ai lancé la fonction jusqu'a 10000 et le mirc n'a pas planté.

A voir également

Ajouter un commentaire

Commentaires

Kerrigan
Messages postés
708
Date d'inscription
lundi 15 juillet 2002
Statut
Membre
Dernière intervention
17 mars 2005

j'ai trouvé beaucoup mieux pour aller plus loin :
les hastables ça castagne je suis allée très loin avec c'est encore plus rapide que le file handling

mais je n'ai pas posté ça parce que j'estime que ce qui est présenté est deja pas trop mal . et puis comme c'est une source qui ne sert a rien donc bon ... c'est marrant quand meme ça montre un peu les difficulté de factorisé des grands nombre (clé du cryptage rsa si je me rapelle bien) avec des nombre premier

ya trop de calcul !!!!!!!!
cs_Melnofil
Messages postés
71
Date d'inscription
dimanche 23 juin 2002
Statut
Membre
Dernière intervention
1 février 2008

"pour coder des ip on peut utiliser des nombres premiers" <== Mouahaha exactement ce que je cherche comment t'a deviné ;)
Bon y'a rien sur ce site (ben quoi on peut toujours rêver ?) j'ai plus qu'a le faire moi-même -__-

Un commentaire sur la source comme même ^_^ :
Je vois pour tes 2 codes les commentaires suivants :
v1) "eviter tous les chiffres superieurs a 2400"
v2) "J'ai lancé la fonction jusqu'a 10000 et le mirc n'a pas planté."
Autant te prevenir tout de suite 10000 ca sert à rien, mieux vaut encore utiliser l'algo de l'autre zouarve.

Si tu veut pas que ton mirc plante utilise des timers pour faire des pauses, genre au début tu fais un truc du genre :
var %timeout $calc($ticks + 1000))
Et dès que tu trouve un nouveau nombre premier tu teste si on a dépassé la valeur de timeout. Si oui, tu arrête l'algorithme et tu lance un timer (avec un délai de l'ordre d'une seconde) pour relancer la fonction sur la suite (mémorise l'endroit ou tu en es !)
Ca va multiplier le temps d'execution par 2 ou plus mais au moins le reste de mirc aura un peu de processeur pour lui :p
Kerrigan
Messages postés
708
Date d'inscription
lundi 15 juillet 2002
Statut
Membre
Dernière intervention
17 mars 2005

dans le cadre de certaine encryption il est tres utile d'avoir une liste de nombres premiers sous la main pour pouvoir factoriser des grands nombres. Disont juste que pour coder des ip on peut utiliser des nombres premiers ... Mais je ne vais pas rentrer dans les details ...
cs_HeXoR
Messages postés
165
Date d'inscription
mercredi 29 janvier 2003
Statut
Membre
Dernière intervention
15 avril 2010

jpréfère quand même truc c carrément plus rapide et c pas limité au nombre 10000 :) et aussi je vois pas à quoi ça sert d'avoir les nombres premiers de 0 à x ?? moi un nombre me suffit, alors si jveux savoir si 37539 est premier jai pas bsoin de savoir si les nombres inférieurs le sont...
Kerrigan
Messages postés
708
Date d'inscription
lundi 15 juillet 2002
Statut
Membre
Dernière intervention
17 mars 2005

merci SornDrixer on va modifier ça pour optimiser le monstre. mais on seras tjs en temps exponetiel alors qu'il nous en faudrait en temps polynomial. j'aimerais bien trouvé le test de "Lucas" ou l'algo de "P. Reisel" si ça traine quelque part chez vous hesitez a m'en faire part

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.