Nombre premiers

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

Messages : 1836

Enregistré le : 01 août 2007 15:04

Classe : américaine!

Localisation : C'est idéal.

Re: Nombre premiers

Message par gardener » 14 févr. 2011 08:18

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.

Messages : 1103

Enregistré le : 18 nov. 2010 21:05

Classe : MPSIB (Hoche)

Re: Nombre premiers

Message par weldan6 » 14 févr. 2011 09:21

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)

Messages : 155

Enregistré le : 16 déc. 2009 19:17

Classe : MPSI

Re: Nombre premiers

Message par Erylis » 14 févr. 2011 10:59

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.

Messages : 1418

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

Re: Nombre premiers

Message par Valvino » 14 févr. 2011 11:04

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/Cour ... uclide.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.

Messages : 1103

Enregistré le : 18 nov. 2010 21:05

Classe : MPSIB (Hoche)

Re: Nombre premiers

Message par weldan6 » 14 févr. 2011 11:48

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)

Messages : 155

Enregistré le : 16 déc. 2009 19:17

Classe : MPSI

Re: Nombre premiers

Message par Erylis » 14 févr. 2011 12:00

De mon côté je parlais des vecteurs :wink:

Messages : 11339

Enregistré le : 30 juil. 2008 16:59

Classe : Dr.-Ing

Re: Nombre premiers

Message par fakbill » 14 févr. 2011 14:19

Outch ce thread en dit long sur les connaissances de base de chez de base en algo du taupin moyen :(

Je sais bien qu'on ne peut pas tout faire mais il serait tout de même bon de dire que la décomposition en facteurs premiers est un algo "très gourmand en temps" (on peut juste s'en tenir à cette vague remarque) et que donc, en pratique, on ne décompose en facteurs premiers que sous la torture.

Je ne demande pas quand explique à tout le monde que l'inversion de matrice coute autant (et non plus) que la multiplication car ca c'est relativement contre intutif est délicat à faire sentir. Par contre, comment faire le chapitre sur les systèmes linéaires sans dire rapidement ce qu'est un gros système pour une machine de bureau de base en 2011??? Après on s'étonne de voir des gens avoir peur de demander une inversion numérique 10x10 à un logiciel (je ne demande même pas qu'on leur parle de régularisation...juste leur dire que 10x10 c'est vraiment rien de rien).
Même remarque pour tous les algo "numériques" vu en maths.
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.

Messages : 5614

Enregistré le : 14 juin 2005 19:29

Re: Nombre premiers

Message par Ragoudvo » 14 févr. 2011 14:33

weldan6 a écrit :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
Ca marche pour un petit nombre (323 en l'occurrence), mais ça n'est pas généralisable, pour la raison donnée par fakbill. Deux fois valent mieux qu'une pour les choses importantes : TROUVER LA DECOMPOSITION EN NOMBRES PREMIERS, C'EST CHER (en l'état actuel des connaissances). Et heureusement que c'est cher ! Si ça n'était pas cher, vous ne pourriez pas acheter votre billet de train sur Internet (je laisse cette réflexion à votre sagacité).

Euclide, c'est la bonne façon de trouver le pgcd (et de trouver des témoins de Bézout aussi d'ailleurs).
fakbill a écrit :Même remarque pour tous les algo "numériques" vu en maths.
Je suis bien d'accord, mais... Sauf erreur, on ne voit que l'algo d'Euclide en prépa ;) (ou presque !)

Messages : 1836

Enregistré le : 01 août 2007 15:04

Classe : américaine!

Localisation : C'est idéal.

Re: Nombre premiers

Message par gardener » 14 févr. 2011 16:09

Euclide, pivot de Gauss, exponentiation rapide. Point !
Doctorant Maths-Info, ancien ENS Cachan.

Messages : 1095

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

Re: Nombre premiers

Message par Necklor » 14 févr. 2011 18:56

fakbill a écrit :Outch ce thread en dit long sur les connaissances de base de chez de base en algo du taupin moyen :(
Je sais bien qu'on ne peut pas tout faire mais il serait tout de même bon de dire que la décomposition en facteurs premiers est un algo "très gourmand en temps" (on peut juste s'en tenir à cette vague remarque) et que donc, en pratique, on ne décompose en facteurs premiers que sous la torture.
Là n'est pas la question. Il s'agit d'avoir en revue des méthodes c'est tout. Si leur prof leur a demandé de le faire sans qu'ils aient vu avec l'algorithme d'Euclide, c'est légitime, ça leur permet de chercher une autre méthode : aucune manière de faire est à négligée, on demande bien de démontrer des résultats d'algèbre sans passer par des théorèmes "puissants" de réduction par exemple, ne serait-ce que pour former l'esprit à voir les différentes méthode pour accéder au même résultat. C'est toujours formateur.
on ne décompose en facteurs premiers que sous la torture
Il n'y a pas de meilleure méthode, ou de solution unique en maths. Il se peut que dans un énoncé on définissent un ensemble d'entiers, de telle manière a ce qu'il soit impossible de calculer leur pgcd avec l'algorithme d'Euclide, mais en passant par leur décomposition en facteurs premiers.

Maintenant répéter que c'est gourmand en temps alors que ça a été dit à je ne sais combien de reprise : c'est évident que c'est couteux, dans ce cas bien précis, pour peu que l'on réfléchisse 3 secondes :roll:
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]

Répondre