logo

Algorithme de décomposition en facteurs premiers


algorithmiqueAlgorithme de décomposition en facteurs premiers

#msg2492304#msg2492304 Posté le 11-07-09 à 12:50
Posté par Profilshrike shrike

Et oui, grand débutant des algorithmes, je me permets de demander encore de l'aide. Seulement cette fois-ci, j'ai fait quelque chose (qui ne marche pas bien entendu ) et donc je cherche une solution pour décomposer un nombre en facteurs premiers.
J'ai essayé de faire des tests de divisions successives par des nombres premiers, et d'ajouter ces nombres, s'ils sont des diviseurs du nombre à décomposer, dans une liste, pour à la fin demander d'afficher la liste. Mais la calculette ne dispose pas de la fonction isprime(x), et j'ai besoin de cette fonction, sans quoi l'algorithme devient tellement long que je n'y comprend plus rien.

Merci de vos suggestions.
re : Algorithme de décomposition en facteurs premiers#msg2492310#msg2492310 Posté le 11-07-09 à 13:02
Posté par ProfilJ-P J-P Correcteur

Il suffit de créer un équivalent à "isprime()"

En voila un en Basic :

Il faut l'adapter en fonction du langage de programmation utilisé.

Publicité

re : Algorithme de décomposition en facteurs premiers#msg2492311#msg2492311 Posté le 11-07-09 à 13:12
Posté par Profilshrike shrike

Le langage est ti-basic, c'est pour une calculatrice graphique texas instrument. Et je précise aussi que je ne connais que le ti-basic, aucun autre langage de programmation...^^ donc merci mais je ne comprends pas grand chose au Visual Basic.

Merci encore

Shrike
re : Algorithme de décomposition en facteurs premiers#msg2492364#msg2492364 Posté le 11-07-09 à 16:20
Posté par Profilshrike shrike

f\left( n\right) = 2 + \left( {2 \left((n-1)! \right)} \mathrm{mod}(n))

si f(n)=2, le nombre n'est pas premier.
si f(n)=n, le nombre est premier

voilà qui peut m'aider...
re : Algorithme de décomposition en facteurs premiers#msg2492404#msg2492404 Posté le 11-07-09 à 17:44
Posté par Profilshrike shrike

Est-ce que quelqu'un peut me confirmer ça. Je me sers ici du théorème de Wilson. Le test à la calculatrice ne fonctionne pas, car celle-ci arrondie les valeurs infiniment petites à 0, ce qui me donne des résultats faux. J'ai pu constater ça grâce à maple.

Voici mon algorithme :

L'utilisateur entre un nombre N.
Si ce nombre est premier (test de Wilson), on affiche simplement le nombre, car il est sa propre décomposition.

Si ce n'est pas le cas, on initialise un nombre C. Si ce nombre C est lui aussi premier, ET qu'il divise le nombre N, on affiche C, et on reteste avec C+1. Dans tous les autres cas, on reteste ça avec C+1. (Il faut les deux conditions réunies pour afficher C). Le tout tant que C<N évidemment.

partDec(x) est la partie décimale de x, soit (x-floor(x))

VARIABLES
  N EST_DU_TYPE NOMBRE
  C EST_DU_TYPE NOMBRE
DEBUT_ALGORITHME
  LIRE N
  SI (partDec(((N-1)!+1)/N=0) ALORS
    DEBUT_SI
    AFFICHER N
    FIN_SI
    SINON
      DEBUT_SINON
      C PREND_LA_VALEUR 2
      TANT_QUE (C<N) FAIRE
        DEBUT_TANT_QUE
        SI (partDec(((C-1)!+1)/C)=0) ALORS
          DEBUT_SI
          SI (partDec(N/C)=0) ALORS
            DEBUT_SI
            AFFICHER N
            C PREND_LA_VALEUR C+1
            FIN_SI
            SINON
              DEBUT_SINON
              C PREND_LA_VALEUR C+1
              FIN_SINON
          FIN_SI
          SINON
            DEBUT_SINON
            C PREND_LA_VALEUR C+1
            FIN_SINON
        FIN_TANT_QUE
      FIN_SINON
FIN_ALGORITHME

Répondre à ce sujet

réservé Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster
attention Un modérateur est susceptible de supprimer toute contribution qui ne serait pas en relation avec le thème de discussion abordé, la ligne éditoriale du site, ou qui serait contraire à la loi.

  • Ce topic

    imprimer Imprimer
    réduire la tailleRéduire   /   agrandir la tailleAgrandir

    Pour plus d'options, connection connectez vous !
  • Fiches de maths



maths - prof de maths - cours particuliers haut de pagehaut Retrouvez cette page sur ilemaths l'île des mathématiques
© Tom_Pascal & Océane 2014