Révolution

[Mika-El]

on cherche à savoir si n est un nombre premier ou pas le + simplement possible
Les nombres premiers, il semble que la seule relation par laquelle ils soient reliés c'est le fait qu'il n'existe pas a et b entiers tel que ab=n. (en ne considérant pas 1 ni n)

Peut-être qu'une autre relation les relie.
Mais pour la trouver, cette autre relation, il faut qu'on se débrouille.
Il faut partir du départ, il ne faut pas oublier que la seule chose qu'on sait pour l'instant c'est*:

Les nombres premiers, il semble que la seule relation par laquelle ils soient reliés c'est le fait qu'il n'existe pas a et b entiers tel que ab=n. (en ne considérant pas 1 ni n)

On peut certes essayer d'inventer, au pif, une relation, en comparant les nombres premiers.
Mais cela paraît hasardeux.


Il semblerait donc qu'on soit obligés de diviser le nombre par tous les nombres premiers plus petits que sa racine.
Certes.
Mais on peut simplifier.
Il suffit de multiplier les nombres premiers + petits que sa racine entre eux.
Après, on devra diviser notre nombre qu'on suspecte d'être premier par ce produit.

Et il n'y aura plus qu'à comparer par rapport à une référence pour savoir si le nombre est premier ou pas.



Cela me paraît fichtrement vrai donc je compte sur vous pour me faire revenir à la réalité!!
-----

[gg0]

Bonsoir.

Inutile de réinventer la roue.
Mais comme je n'ai pas bien compris ta méthode, peux-tu l'appliquer à 1073741827 ?

Cordialement.

NB : Comme je soupçonne ton message de n'être que du baratin, évite de baratiner, donne l'explication précise de la méthode dont tu parles.

[Mika-El]

Mon but est simplement de simplifier la méthode pour savoir si un nombre est premier ou pas.
Ce qui permettrait de connaître beaucoup + de nombres premiers.

Comment savoir si un nombre n est multiple de 2 ou multiple de 3... mais en faisant 1seul calcul?

On va diviser n par 2x3=6

Si le résultat obtenu est ,xyyyyyyyy... -> le nombre n'est pas ni multiple de 2 ni de 3
Si le résultat obtenu est ,yyyyyyyyy... -> le nombre est multiple de 2 mais pas de 3
Si le résultat obtenu est ,x -> le nombre obtenu est multiple de 3
Si le résultat obtenu est un entier -> le nombre est multiple de 6

Ici, n est un nombre entier.

Cela permettrait de faire une seule division pour savoir si un nombre est multiple de 2 trucs.
Bien sûr le but étant d'améliorer tout cela pour n'avoir besoin de faire qu'une seule division et savoir si un nombre est multiple de 3, puis 4, puis 100trucs.

[Mika-El]

La virgule n'est pas forcément bien placée dans mon exemple.
Ca dépend de la taille de n.

Il suffit de multiplier le résultat par un facteur 10 qui dépend de la taille de n

[A voir en vidéo sur Futura]

[Mika-El]

Mon but est simplement de simplifier la méthode pour savoir si un nombre est premier ou pas.
Ce qui permettrait de connaître beaucoup + de nombres premiers.

Comment savoir si un nombre n est multiple de 2 ou multiple de 3... mais en faisant 1seul calcul?

On va diviser n par 2x3=6

Si le résultat obtenu est ,abcdefghijklm... -> le nombre n'est pas ni multiple de 2 ni de 3 (exemple : 51.54793148964...)
Si le résultat obtenu est ,yyyyyyyyy... -> le nombre est multiple de 2 mais pas de 3 (exemple : 2.666666....)
Si le résultat obtenu est ,x -> le nombre obtenu est multiple de 3
Si le résultat obtenu est un entier -> le nombre est multiple de 6

Ici, n est un nombre entier.

Cela permettrait de faire une seule division pour savoir si un nombre est multiple de 2 trucs.
Bien sûr le but étant d'améliorer tout cela pour n'avoir besoin de faire qu'une seule division et savoir si un nombre est multiple de 3, puis 4, puis 100trucs.

Rectifications, désolé.
Et l'autre truc, on oublie:

La virgule n'est pas forcément bien placée dans mon exemple.
Ca dépend de la taille de n.

Il suffit de multiplier le résultat par un facteur 10 qui dépend de la taille de n

[Tryss]

Par exemple, pour n=2*3*5*7=210





Tu fais comment la différence? (la barre veut dire que c'est la partie qui se répète à l'infini)

[Mika-El]

Par exemple, pour n=2*3*5*7=210





Tu fais comment la différence? (la barre veut dire que c'est la partie qui se répète à l'infini)

J'en sais rien.
Mais j'ai quand même réussi à réduire le nombre de divisions à réaliser pour savoir si un nombre est premier ou pas. Non?
C'est pas mal, faut y aller doucement pour diminuer davantage

[gg0]

Bonjour.

Tu es en train d'inventer l'eau tiède !!
Des tas de gens depuis 2500 ans ont réfléchi à cette question, généralement en s'appuyant sur les idées de leurs prédecesseurs. L'idée de multiplier les premiers entiers premiers est connue depuis longtemps (elle est utilisée par exemple par Maple) et utilisée bien plus utilement que ce que tu proposes (pgcd). la question de savoir si un entier est premier est résolue de façon ultra-rapide (avec les logiciels actuels - vois Xcas, par exemple) lorsqu'ils ont peu de chiffres (jusqu'à 20 ou 30). par exemple mon ordinateur avec une vieille version de Maple donne la décomposition en facteurs premier de 123456789101112131415161718192 023 en moins d'une seconde : 149*151*115454141723*108156479 2993*43943.

Cordialement.

[taladris]

En gros, ta méthode ne marche que pour 2 et 3?

Moi, je peux savoir si un nombre est divisable par 2, 3, 4, 5 et 11 (je peux rajouter gratuitement 9 et 25 mais ce ne sont pas des nombres premiers) en non pas 6 ni 5 ni même 1 division, mais sans aucune division! Juste deux petites additions.

[taladris]

Bonjour.

Tu es en train d'inventer l'eau tiède !!
Des tas de gens depuis 2500 ans ont réfléchi à cette question, généralement en s'appuyant sur les idées de leurs prédecesseurs. L'idée de multiplier les premiers entiers premiers est connue depuis longtemps (elle est utilisée par exemple par Maple) et utilisée bien plus utilement que ce que tu proposes (pgcd). la question de savoir si un entier est premier est résolue de façon ultra-rapide (avec les logiciels actuels - vois Xcas, par exemple) lorsqu'ils ont peu de chiffres (jusqu'à 20 ou 30). par exemple mon ordinateur avec une vieille version de Maple donne la décomposition en facteurs premier de 123456789101112131415161718192 023 en moins d'une seconde : 149*151*115454141723*108156479 2993*43943.

Cordialement.

Petite précision: sauf erreur, savoir si un nombre est premier est un problème facile et peut se faire avec des algorithmes probabilistes. Par contre, connaître les facteurs premiers d'un grand nombre composé est un problème très difficile (en temps de calcul). C'est le principe de base du système de cryptage RSA de nos cartes bleues.

[Mika-El]

Okay, merci,
Mais n'existe-t-il pas une suite permettant de trouver les nombres premiers?
Par exemple :

=1

=2

=3

=5

=7

=11

=13

...

Si c'était le cas, on saurait calculer des nombres premiers avec une longueur aussi longue que l'on souhaite
Or, dans wikipédia on trouve : http://fr.wikipedia.org/wiki/Nombre_premier

25 janvier 2013 Curtis Cooper, G. Woltman, S. Kurowski, et al. mer 2,
University of Central Missouri
(Projet GIMPS) Nombre de Mersenne M57885161 257 885 161 - 1
17 425 170 chiffres GIMPSmer 3

Ma question : pourquoi le + grand nombre premier conu n'a que 17425170 chiffres (et pourquoi des mecs se sont emmerdés à le trouver)?

[Mika-El]

Je suis désolé.
Je pose trop de questions.

Mais c'est le fait de ne pas savoir qui m'énerve.
Pourquoi est-ce que on dit qu'on ne sait pas?

Pour moi, en maths, on sait tout.

On essaie, à partir d'un problème, de rejoindre un autre problème équivalent (avec les mêmes solutions).
Il faut apprendre par coeur comment faire pour trouver cet autre problème équivalent (exemple : multiplier par un même nombre des 2côtés d'une égalité dans notre cas où les unités sont toutes identiques) ou bien on va mettre beaucoup de temps pour résoudre notre problème.
Mais c'est tout.

Ce qui me dérange c'est ce prix du millénaire.
http://fr.wikipedia.org/wiki/Probl%C3%A8me_P_%3D_NP
Le prix qui dit que peut-être P=NP, c'est-à-dire que peut-être que il faut autant de temps pour vérifier un résultat que pour obtenir un résultat.

Je ne comprends pas ça.

Imaginons que je veux un nombre premier + grand que 1 000 000 000.
Si je veux le trouver, je serais obligé de tester plusieurs nombres supérieurs à 1 000 000 000 pour trouver un qui soit bon.

Mais la vérification ce serait vachement plus simple puisqu'il suffirait de faire les mêmes calculs qui ont permis de dire que j'ai trouvé le nombre que j'ai cherché, sans faire les calculs sur d'autres nombres qui se sont avérés pas premiers.

[gg0]

Bonsoir.

Je pose trop de questions.

Mais c'est le fait de ne pas savoir qui m'énerve.

Alors prends le temps d'apprendre : Etudie un bon livre de théorie des nombres.

Pour moi, en maths, on sait tout.

Faux.

Je ne comprends pas ça.

Normal, tu parles de choses que tu ne comprends pas ... prends le temps d'étudier les maths avant d'en parler à tort et à travers.

La fin de ton message est incompréhensible.

Mais globalement, tu sembles disperser ta pensée sur des fausses idées des maths. Apprend-les vraiment. là tu ressemble au supporter de foot qui engueule les joueurs sur le terrain en les traitant de fainéant alors qu'il est incapable de courir 100 m !

Tu es intelligent, utilise ton intelligence pour apprendre vraiment, sors de la vulgarisation mal faite et mal comprise, ne rêve pas mais fais des maths...

Cordialement.