Inscription / Connexion Nouveau Sujet
Niveau algorithmique
Partager :

Algorithme de décomposition en facteurs premiers

Posté par
shrike
11-07-09 à 12:50

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.

Posté par
J-P Correcteur
re : Algorithme de décomposition en facteurs premiers 11-07-09 à 13:02

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

En voila un en Basic :

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

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

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

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

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...

Posté par
shrike
re : Algorithme de décomposition en facteurs premiers 11-07-09 à 17:44

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

Seuls les membres peuvent poster sur le forum !

Vous devez être connecté pour poster :

Connexion / Inscription Poster un nouveau sujet
Une question ?
Besoin d'aide ?
(Gratuit)
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.


Vous devez être membre accéder à ce service...

Pas encore inscrit ?

1 compte par personne, multi-compte interdit !

Ou identifiez-vous :


Rester sur la page

Désolé, votre version d'Internet Explorer est plus que périmée ! Merci de le mettre à jour ou de télécharger Firefox ou Google Chrome pour utiliser le site. Votre ordinateur vous remerciera !