Nombre premiers

[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

[weldan6]

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.

[Erylis]

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]

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.

[weldan6]

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

[Erylis]

De mon côté je parlais des vecteurs

[fakbill]

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.

[Ragoudvo]

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

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 !)

[gardener]

Euclide, pivot de Gauss, exponentiation rapide. Point !

[Necklor]

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