Nombre premiers
Re: Nombre premiers
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 ) 391 aussi donc t'as plus qu'a simplifier.
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 ) 391 aussi donc t'as plus qu'a simplifier.
Re: Nombre premiers
Malheuresement oui... En seconde en tout cas.Silvere Gangloff a écrit :C'est sérieux ??Necklor a écrit :Au lycée les vecteurs vont être supprimés du programme, alors pour ce qui est de l'algorithme d'Euclide..
Re: Nombre premiers
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.gardener a écrit :Euclide est évidemment polynomial en la taille de nombres et non logarithmiqueValvino 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.
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.
Re: Nombre premiers
Erylis a écrit :Malheuresement oui... En seconde en tout cas.Silvere Gangloff a écrit :C'est sérieux ??Necklor a écrit :Au lycée les vecteurs vont être supprimés du programme, alors pour ce qui est de l'algorithme d'Euclide..
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...
Re: Nombre premiers
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.
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é.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Re: Nombre premiers
Euclide, pivot de Gauss, exponentiation rapide. Point !
Doctorant Maths-Info, ancien ENS Cachan.
Re: Nombre premiers
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.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.
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.on ne décompose en facteurs premiers que sous la torture
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
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]
Re: Nombre premiers
Ragoudvo a écrit :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é).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
Euclide, c'est la bonne façon de trouver le pgcd (et de trouver des témoins de Bézout aussi d'ailleurs).
Je suis bien d'accord, mais... Sauf erreur, on ne voit que l'algo d'Euclide en prépa (ou presque !)fakbill a écrit :Même remarque pour tous les algo "numériques" vu en maths.
je suis désolé mais j'ai jamais dit que c'était généralisable, c'est une des nombreuses méthodes et une des plus simple bon c'est sur faut réfléchir en se disant que racine(323) c'est plus petit qu'un gd nombre mais t'inquiete après cette réflexion c'est facile...
Re: Nombre premiers
C'est l'argument qu'on entend encore et toujours. Oui ça l'est MAIS ça n'empeche pas de *préciser* aux élèves que ce n'est pas la fin de l'histoire.C'est toujours formateur.
On ne calcule plus une borne de l'erreur de méthode quand on calcule une intégrale avec des trapèzes ou des rectangles? C'est bien dommage
Pas prof.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.
Prépa, école, M2, thèse (optique/images) ->ingé dans le privé.