Nombre premiers

[java-amin]

Salut!

Comment calculer d=pgcd(323,391)??
Doit-on essayer leur disivisions sur tout les nombres premiers?

[Valvino]

L'algorithme d'Euclide me parait tout à fait approprié. Il est en général trop long (que ce soit à la main ou sur machine) de décomposer des nombres en facteurs premiers, on évite de le faire.

[Necklor]

Salut!

Comment calculer d=pgcd(323,391)??
Doit-on essayer leur disivisions sur tout les nombres premiers?

Tu dois écrire leurs décompositions en facteurs premiers. Tu regardes d'abord si le nombre en question est divisible par 2, dans quel cas tu le divises par 2. Tu vois si cette division donne un nombre encore divisible par 2, dans quel cas tu réitères, dans le cas contraire tu tentes de diviser par 3 et ainsi de suite avec tous les nombres premiers. Une fois que tu as les décompositions des 2 nombres en nombres premiers : $ \prod_{i=1}^{n} p_i^{\alpha_i} $ et $ \prod_{i=1}^{m} p_i^{\beta_i} $ avec $ p_1 = 2 $, $ p_2 = 3 $.... tu as facilement le pgcd, qui est : $ \prod_{i=1}^{Min(n,m)} p_i^{Min(\alpha_i, \beta_i)} $

[Valvino]

Non non et non c'est très très maladroit de faire comme ça. L'algorithme d'Euclide a une complexité en logarithme (par rapport à la taille des nombres), alors que décomposer un nombre en facteur premier c'est très coûteux on ne connait aucun algo polynomial (par rapport à la taille des nombres) qui le fait.

[Necklor]

Non non et non c'est très très maladroit de faire comme ça. L'algorithme d'Euclide a une complexité en logarithme (par rapport à la taille des nombres), alors que décomposer un nombre en facteur premier c'est très coûteux on ne connait aucun algo polynomial (par rapport à la taille des nombres) qui le fait.

Au temps pour moi, j'ai lu trop vite. Je pensais qu'il voulait le faire avec la décomposition en facteurs premiers.

[LB]

L'algorithme d'Euclide ça te dit rien ?

[Valvino]

Rhooo l'autre comment il lit pas mes posts

[Necklor]

Au lycée les vecteurs vont être supprimés du programme, alors pour ce qui est de l'algorithme d'Euclide..

[Silvere Gangloff]

Au lycée les vecteurs vont être supprimés du programme, alors pour ce qui est de l'algorithme d'Euclide..

C'est sérieux ??

[gardener]

Non non et non c'est très très maladroit de faire comme ça. L'algorithme d'Euclide a une complexité en logarithme (par rapport à la taille des nombres), alors que décomposer un nombre en facteur premier c'est très coûteux on ne connait aucun algo polynomial (par rapport à la taille des nombres) qui le fait.

Euclide est évidemment polynomial en la taille de nombres et non logarithmique