Nombre premiers

Un problème, une question, un nouveau théorème ?

Messages : 16

Enregistré le : 13 févr. 2011 22:01

Classe : MPSI

Nombre premiers

Message par java-amin » 13 févr. 2011 22:05

Salut!

Comment calculer d=pgcd(323,391)??
Doit-on essayer leur disivisions sur tout les nombres premiers?
1-J'ai eu la faute, J'ai eu la faute, J'ai eu la faute.Mais je l'est commis.(junior-maths)

2-Chacun de nous porte un fou sous son manteau, mais certains le dissimulent mieux que d'autres

Messages : 1418

Enregistré le : 31 août 2006 11:59

Re: Nombre premiers

Message par Valvino » 13 févr. 2011 22:22

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.

Messages : 1095

Enregistré le : 03 déc. 2010 21:13

Re: Nombre premiers

Message par Necklor » 13 févr. 2011 22:31

java-amin a écrit :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)} $
Modifié en dernier par Necklor le 13 févr. 2011 22:42, modifié 1 fois.
Chat d'entraide mathématiques : #les-mathematiques sur le réseau IRC Epiknet (irc.epiknet.org) ou en un clic via le lien : [url]irc://irc.epiknet.org/les-mathematiques[/url]

Messages : 1418

Enregistré le : 31 août 2006 11:59

Re: Nombre premiers

Message par Valvino » 13 févr. 2011 22:41

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.

Messages : 1095

Enregistré le : 03 déc. 2010 21:13

Re: Nombre premiers

Message par Necklor » 13 févr. 2011 22:45

Valvino a écrit :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.
Chat d'entraide mathématiques : #les-mathematiques sur le réseau IRC Epiknet (irc.epiknet.org) ou en un clic via le lien : [url]irc://irc.epiknet.org/les-mathematiques[/url]

Avatar du membre
LB

Messages : 1059

Enregistré le : 09 juin 2008 14:14

Localisation : par rapport à un idéal maximal

Re: Nombre premiers

Message par LB » 13 févr. 2011 22:47

L'algorithme d'Euclide ça te dit rien ?
On peut dire que les fonctions convexes en dimension infinie et les fonctions continues en dimension finie sont d’une complexité similaire - Gilles Godefroy
http://perso.eleves.bretagne.ens-cachan.fr/~ldiet783/

Messages : 1418

Enregistré le : 31 août 2006 11:59

Re: Nombre premiers

Message par Valvino » 13 févr. 2011 22:49

Rhooo l'autre comment il lit pas mes posts :mrgreen:

Messages : 5614

Enregistré le : 14 juin 2005 19:29

Re: Nombre premiers

Message par Ragoudvo » 13 févr. 2011 22:51

Sachant que c'est quelque chose qu'on apprend en classe de troisième avec le programme français (si si, on fait encore (peu de) maths au collège), c'est étrange de pas savoir faire ça en sup...

Messages : 1095

Enregistré le : 03 déc. 2010 21:13

Re: Nombre premiers

Message par Necklor » 13 févr. 2011 22:58

Au lycée les vecteurs vont être supprimés du programme, alors pour ce qui est de l'algorithme d'Euclide..
Chat d'entraide mathématiques : #les-mathematiques sur le réseau IRC Epiknet (irc.epiknet.org) ou en un clic via le lien : [url]irc://irc.epiknet.org/les-mathematiques[/url]

Messages : 430

Enregistré le : 18 avr. 2010 17:16

Classe : Normal

Localisation : Paris

Re: Nombre premiers

Message par Silvere Gangloff » 14 févr. 2011 07:04

Necklor a écrit :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 ??

Répondre