Bonsoir,

Ton idée est pas mal : elle repose sur le crible d'Eratostène à ce que j'ai compris, mais le soucis est qu'elle est trop longue, mais l'idée est là : il faut faire une liste des nombres premiers, et regarder quel produit redonne ton nombre de départ.

Il existe des manières plus efficaces de réaliser cette liste.

Il faut pour cela implémenter un test de primalité. Je ne connais pas Algobox, mais il doit surement y avoir une commande qui te donne le reste dans la division euclidienne a de par b. Par la suite, je noterai a % b ce nombre.
Ainsi, a est divisible par b ssi a % b = 0.

Voici une implémentation simple et relativement efficace d'un test de primalité
n : entier
continue : booléen
k : entier
Saisir n
(pour accélérer un peu)

si n = 2 :
Renvoi VRAI

sinon si n % 2 = 0 :
Renvoi FAUX

sinon :
k Prend la valeur 3
continue Prend la valeur VRAI
Tant Que continue = VRAI ET k <= sqrt(n) :
si n % k = 0 :
continue prend la valeur FAUX
sinon k prend la valeur k + 2

Fin Tant Que

Renvoi continue


Maintenant, on peut insérer ce morceau au sein d'un algorithme plus grand, qui va faire la liste des nombres premiers entre 2 et m

L : Type Liste
j : type Entier (c'est l'indice de la liste, que je suppose allant de 0 à longueur_liste -1)

Pour i allant de 2 à m :
Si i est premier (donc si la fonction précédente renvoie la valeur VRAI) :

L[j] prend la valeur i
j prend la valeur j+1

Fin Pour

Ainsi, tu obtiens la liste de tous les nombres premiers susceptibles d'apparaître dans la décomposition de ton nombre

A toi maintenant d'implémenter tout ça.
Je ne sais pas me servir d'Algobox, mais j'espère que tu saisiras l'idée =)

En fait, là où on perd énormément de temps, c'est sur la double boucle tant que de la fin.
En effet, une seule suffit :
Si L est la liste des entiers premiers plus petits que m, et que cette liste est de taille N, alors

Pour i allant de 0 à N-1 :
Si m % L[i] = 0 ET (m / L[i]) est Premier, alors renvoyer ( L[i] , m / L[i])

Ca permet d'économiser pas mal de temps

Merci je vais essayer
Mais une fois que j'ai la liste des nombres premiers comment je trouve les deux facteurs premiers ? Parce que dans mon algorithme c'est pour chercher les deux facteurs à la fin qu'il y a trop de boucles, pas pour établir la liste...

Ah je lis le deuxième message j'avais pas vu

En fait, il s'avère que ta méthode pour générer la liste des nombres premiers est bien plus efficace que la mienne, donc conserve-la
La où ça coinçait, c'était dans la recherche du couple solution.
Du coup, il faut quand même implémenter la test de primalité, générer ta liste de nombres premiers tel que tu l'as fait, et enfin utiliser la recherche du couple grâce à la méthode de mon dernier post

En gardant les notations de mon algorithme de départ, pour traduire "m/p[i] est premier" j'ai essayé "p(m/p[i])!=0" mais il y a "erreur dans l'exécution"... Comment faire ?

Erf c'est vrai que c'est un tableau et on y a accès plus facilement que le type liste abstraite.... Du coup oui il est beaucoup plus pertinent de chercher si m/p[i] n'est pas nul dans le tableau...
Es-tu sûr qu'il ne s'agisse pas d'un problème de syntaxe ?
Normalement ça serait p[m/p[i]] avec des crochets deux fois ?

Bref désolé mais mon pauvre petit test ne servait à rien en fin de compte xD

Effectivement c'était qu'une erreur de syntaxe merci ^_^
Parfait tout marche bien maintenant, finalement 406421=547*743 !
Merci beaucoup en tout cas !

Ah si j'aurais une dernière question : y a-t-il un moyen d'arrêter la boucle "pour .. allant de .. à .." lorsque la condition est remplie, pour gagner un peu de temps ?

Oui bien sûr, il suffit d'utiliser une boucle TANT QUE, qui aurait cette allure :

i Est de Type : Nombre
continuer Est de Type : Booléen

i Prend la valeur 2
Continuer Prend la valeur VRAI

TANT QUE i <= sqrt(m) ET Continuer :
si p[i] =! 0 ET m % p[i] = 0 & p[m/p[i]] != 0 alors : Continuer Prend la Valeur FAUX
sinon : i Prend la valeur i+1
FIN TANT QUE

si Continuer = FAUX alors :
AFFICHER " p[i] * p[m/p[i]] "
sinon :
AFFICHER : " pas de solution "

Bonjour,

mon avis : cet algorithme par construction préalable d'une table des nombres premiers jusqu'à M est peu efficace, en particulier il calcule des tas de nombres premiers inutiles.

sans parler de l'implémentation de la table des nombres premiers qui est "pleine de trous" donc peu efficace, en fait il ne s'agit absolument pas d'une table de nombres premiers mais d'une table d'indicateurs qui pour tous les nombres premiers ou pas mémorise s'il l'est (premier).

et les boucles de boucles pour calculer cette table de nombres premiers
(un tant que dans une boucle pour) seraient bien mieux utilisées pour décomposer directemment M en facteurs premiers, sans crible ni rien, ce qui fait au pire (M)/2 boucles en gros, boucle simples, très largement à la portée d'Algobox. (moins de 320 boucles)

le seul intérêt de créer ainsi une table de nombres premiers serait pour décomposer des listes de nombres en nombres premiers (et pas un seul nombre)
alors ces nombres premiers étant calculés une fois pour toutes, on aurait un gain effectif d'autant plus important qu'on aurait plus de nombres à décomposer.
étant bien entendu que la table de nombres premiers doit être une vraie table qui ne contient que les nombres premiers
p[0] = 2
p[1] = 3
p[2] = 5
p[3] = 7
p[4] = 11 etc

sinon quel intérêt d'être obligé de tester à la fin en fait tous les couples de nombres premiers ou pas ???
les non premiers donnent un produit nul mais ils sont testés quand même !!! inutile et pur gaspillage.

Merci ravinator

mathafou comment obtenir une liste ne contenant que les nombres premiers alors ?

Bonsoir mathafou

Pour pouvoir décomposer M en produits de facteurs premiers, cela ne demande-t-il pas de connaître les-dits facteurs premiers pouvant intervenir dans la décomposition ? Du coup une liste de ceux-ci me semble nécessaire, même si la manière dont on l'a calculée ici laisse plein de trous, non?

Comment ferais-tu ?  

Bof.
et pas de liste du tout ça ne te convient pas ?

pour obtenir une liste de nombres premiers avec le crible d'Eratostène comme tu l'utilises, il faudrait en plus à la fin "compacter" la liste (ce qui est une opération lourde)
mieux faire deux listes :
- le crible
- la liste des nombres premiers dans laquelle on ne met que des nombres premiers au fur et à mesure qu'on les "découvre" dans le crible.

je reprends ton algorithme. (en langage naturel les lourdeurs d'Algobox non merci)

VARIABLES
NOMBRE m, i, j, np
LISTE crible
LISTE p

DEBUT_ALGORITHME
  LIRE m
  np = 0    // nombre de nombres premiers connus : aucun
  POUR i de 2 à m
     |   crible[i] = i  / initialisation du crible (à n'importe quoi  0)
  POUR i de 2 à sqrt(m)
     |   SI (crible[i]!=0)
     |       |  p[np] = i   // un nombre premier trouvé
     |       |  np = np+1
     |       |  j = i
     |       |  TANT_QUE (j<=m)
     |       |      |   j PREND_LA_VALEUR j+i
     |       |      |   crible[j] = 0
// ici on a dans p[0..np-1] la liste sans trous des seuls nombres premiers < m

D'accord merci beaucoup et tu dis qu'on peut le faire sans liste ?

sans table de nombres premiers du tout, et en plus ça donne même la décomposition de n'importe quel nombre pas forcément composé de deux facteurs seulement.

puisque de toute façon on balaye tous les i de 2 à m dans cet ordre, quand on en trouve un qui divise m ce sera un diviseur premier de m (puisqu'il n'y a pas de diviseur plus petit !!)

reste à trouver les autres diviseurs premiers de m
pour cela on divise m par ce diviseur premier là et on continue
ce qui donne :

Variables :
Nombres m, p, e

Algorithme :
lire m
p = 2
tant que p² < m // test plus rapide que via m
e = 0
tant que p divise m // sert en même temp de "si"
m = m/p
e = e+1
si e != 0
// on a un diviseur premier p a l'exposant e : l'afficher
afficher p et e (p^e)
p = p+1
si m != 1
// le reliquat est premier
afficher m
fini.

on peut améliorer le programme en faisant environ deux fois moins de boucles car tous les nombres premiers sauf 2 sont impairs :

Variables :
Nombres m, p, en d

Algorithme :
lire m
p = 2
d = 1
tant que p² < m // test plus rapide que via m
e = 0
tant que p divise m // sert en même temp de "si"
m = m/p
e = e+1
si e != 0
// on a un diviseur premier p a l'exposant e : l'afficher
afficher p et e (p^e)
p = p+d
d = 2 // les suivants sont de deux en deux
si m != 1
// le reliquat est premier
afficher m
fini.

résultat (exemple) :
m = 350202312

2^3
3^3
17
283
337

150 boucles effectuées en tout

PS : errata p² m bien entendu
sinon le programme serait en échec sur un nombre qui serait le carré d'un nombre premier

Merci mathafou ! En effet je n'avais jamais réalisé que le premier diviseur que l'on trouverait serait premier. Du coup certes ça va beaucoup plus vite.

Ah oui j'avais pas pensé que faire la décomposition en facteurs premiers marcherait même s'il n'y a que deux facteurs ^_^ (=> go apprendre le théorème fondamental de l'arithmétique)
En plus j'en avais déjà fait un comme ça qui ressemble au tien il y a pas longtemps
Merci *_*