Nombre premiers

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

Modérateurs : JeanN, Michel Quercia

java-amin
Messages : 16
Enregistré le : dim. févr. 13, 2011 11:01 pm
Classe : MPSI

Nombre premiers

Message par java-amin » dim. févr. 13, 2011 11:05 pm

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

Valvino
Messages : 1418
Enregistré le : jeu. août 31, 2006 11:59 am

Re: Nombre premiers

Message par Valvino » dim. févr. 13, 2011 11:22 pm

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
Messages : 1095
Enregistré le : ven. déc. 03, 2010 10:13 pm

Re: Nombre premiers

Message par Necklor » dim. févr. 13, 2011 11:31 pm

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 dim. févr. 13, 2011 11:42 pm, 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 : irc://irc.epiknet.org/les-mathematiques

Valvino
Messages : 1418
Enregistré le : jeu. août 31, 2006 11:59 am

Re: Nombre premiers

Message par Valvino » dim. févr. 13, 2011 11:41 pm

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
Messages : 1095
Enregistré le : ven. déc. 03, 2010 10:13 pm

Re: Nombre premiers

Message par Necklor » dim. févr. 13, 2011 11:45 pm

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 : irc://irc.epiknet.org/les-mathematiques

Avatar du membre
LB
Messages : 1059
Enregistré le : lun. juin 09, 2008 2:14 pm
Localisation : par rapport à un idéal maximal

Re: Nombre premiers

Message par LB » dim. févr. 13, 2011 11:47 pm

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/

Valvino
Messages : 1418
Enregistré le : jeu. août 31, 2006 11:59 am

Re: Nombre premiers

Message par Valvino » dim. févr. 13, 2011 11:49 pm

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

Avatar du membre
Ragoudvo
Messages : 5614
Enregistré le : mar. juin 14, 2005 7:29 pm

Re: Nombre premiers

Message par Ragoudvo » dim. févr. 13, 2011 11:51 pm

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

Necklor
Messages : 1095
Enregistré le : ven. déc. 03, 2010 10:13 pm

Re: Nombre premiers

Message par Necklor » dim. févr. 13, 2011 11:58 pm

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 : irc://irc.epiknet.org/les-mathematiques

Avatar du membre
Silvere Gangloff
Messages : 430
Enregistré le : dim. avr. 18, 2010 5:16 pm
Classe : Normal
Localisation : Paris
Contact :

Re: Nombre premiers

Message par Silvere Gangloff » lun. févr. 14, 2011 8:04 am

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

Avatar du membre
gardener
Messages : 1836
Enregistré le : mer. août 01, 2007 3:04 pm
Classe : américaine!
Localisation : C'est idéal.
Contact :

Re: Nombre premiers

Message par gardener » lun. févr. 14, 2011 9:18 am

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.


Euclide est évidemment polynomial en la taille de nombres et non logarithmique ;)
Doctorant Maths-Info, ancien ENS Cachan.

Avatar du membre
weldan6
Messages : 1103
Enregistré le : jeu. nov. 18, 2010 10:05 pm
Classe : MPSIB (Hoche)

Re: Nombre premiers

Message par weldan6 » lun. févr. 14, 2011 10:21 am

pgcd(323;391)=pgcd(19*17;23*17)=17pgcd(19;23)=17*1=17
car 19 et 23 sont premiers donc premiers entre eux.
C'est tout simple.
Terminale powaaaaaaaaaa.

Nan plus sérieusement pour comment faire j'ai d'abord rgder si 323 était premier, s'il est premier il est divisible par aucun des nombres entiers naturels inférieurs à sa racine carrée
racine(323)=17.9
après t'essaye a la calculatte en 2s et 323 est divisble par 17 et coup de bol (ou pas :mrgreen: ) 391 aussi donc t'as plus qu'a simplifier.
2010/2011 : TS Lycée La Bruyère (Versailles)
2011/2013 : MPSI/MP Lycée Hoche (Versailles)

Erylis
Messages : 155
Enregistré le : mer. déc. 16, 2009 8:17 pm
Classe : MPSI

Re: Nombre premiers

Message par Erylis » lun. févr. 14, 2011 11:59 am

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


Malheuresement oui... En seconde en tout cas.

Valvino
Messages : 1418
Enregistré le : jeu. août 31, 2006 11:59 am

Re: Nombre premiers

Message par Valvino » lun. févr. 14, 2011 12:04 pm

gardener a écrit :
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.


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


Oui j'ai dit n'importe quoi mea culpa. En fait c'est le nombre de divisions euclidiennes à effectuer qui est en log du deuxième nombre : http://www.mat.ulaval.ca/fileadmin/Cours/HST-2901/A10_ComplexiteEuclide.pdf.

Mais bon ca ne change rien à ce que j'ai dis, qu'il faut privilégier cet algo plutôt que de décomposer en facteurs premiers.

Avatar du membre
weldan6
Messages : 1103
Enregistré le : jeu. nov. 18, 2010 10:05 pm
Classe : MPSIB (Hoche)

Re: Nombre premiers

Message par weldan6 » lun. févr. 14, 2011 12:48 pm

Erylis a écrit :
Silvere Gangloff a écrit :
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 ??


Malheuresement oui... En seconde en tout cas.



Pour ce qui est de l'algorithme d'Euclide il est connu depuis le college (5e je crois), après au lycée c'est seulement dans le programme des TS spé maths.
De toute façon c'est quasi impossible qu'il ne soit plus étudié car la moitié de l'année de spé maths c'est l'arithmétique et bon faire de l'arithmétique sans étudier ce bon vieux Euclide...
2010/2011 : TS Lycée La Bruyère (Versailles)
2011/2013 : MPSI/MP Lycée Hoche (Versailles)

Répondre

Qui est en ligne

Utilisateurs parcourant ce forum : Aucun utilisateur enregistré et 11 invités