Une façon autre de rechercher les nombres premiers?

[Porte7]

Bonjour,
Dans cet algorithme j’ai utilisé une formule pour rechercher les nombres premiers.
A vous de juger s’il vous plaît, merci

#include <stdio.h>
#include <stdlib.h>
#include <new>

int main()
{
int N=0,compteur=1, x=1;
 int val ;
 printf ( "Programme Personnel basé sur le programme de recherche des NP à partir des carrés des precurseurs aux NP.  \nVeuillez insérer un nombre limite  en dessous duquel tous les nbres premiers seront calculés : " ) ; 
   scanf("%d", &val); 
   bool * Tableau2 = new bool [val];    
                  while ( compteur >0)
                  {
                  for (int y =0 ; N < val ; y++)
                  {
                      
                  N = 4*x*x + 4*x + 1 + y*(4*x + 2);  // formule utilisée 
                  
                  Tableau2[N]=1;
                  compteur = y ;
                  }
                  x++; N = 0; compteur--;
                  }
           for (int i =3; i < val; i = i+2)
                 {
                     if (Tableau2[i]==0  )
                     {  
                     printf("   %d", i);
                     }
  
  }
}

Ci joint une copie d’ecran:

-----

[gg0]

Bonjour.

Tu as trouvé un programme de calcul des petits nombres premiers. Bravo! Mais ça n'a rien de nouveau. Et comme on est ici sur un forum de maths, ce qui nous intéressera c'est que tu donnes la méthode mathématique utilisée, qu'on puisse la tester et la démontrer. Et peut-être (*) voir si elle serait plus efficace que les méthodes connues. Sur mon vieil ordinateur, avec une très ancienne version de Maple, j'obtiens les premiers de 3 à 997 en un vingtième de seconde (essentiellement du temps d'affichage).

Cordialement.

(*) si un spécialiste passe.

[Porte7]

Bonjour,
Vous avez testé donc ce programme ?
En attendant je peux déjà dire que la formule 4x² + 4x + 1 + 4xy + 2y donne tous les nombres impairs non premiers quand x est défini sur N* et y sur N.
Comme je ne suis pas mathématicien je me réserve encore un peu de temps pour essayer de vous donner une réponse un peu plus précise autant que faire ce peux. Cdlt

[Deedee81]

Salut,

En attendant je peux déjà dire que la formule 4x² + 4x + 1 + 4xy + 2y donne tous les nombres impairs non premiers quand x est défini sur N* et y sur N.

Ca c'est une évidence !!!!!

[A voir en vidéo sur Futura]

[pm42]

Ca c'est une évidence !!!!!

D'autant que x=1, y=-1 donne 3 qui est premier donc c'est mal barré.

[Deedee81]

D'autant que x=1, y=-1 donne 3 qui est premier donc c'est mal barré.

Je n'ai pas réagit sur "ne donne QUE des non premiers" mais sur "donne TOUS les nombres non premiers" (qui est archi évident)
Mais j'aurais dû ajouter "mais elle ne donne pas que ça" ci-dessus. D'autant que j'y ai pensé !!!!

Donc merci

J'ai mieux comme formule : x, avec x parcourant N : donne aussi tous les impairs non premiers
(je rigole, mais à peine, car j'ai bien compris que le but de la formule est d'être un peu plus performant bien que le gain soit faible, c'est archi connu comme algorithme.
C'est du Eratosthene et ses très nombreuses variantes)

[gg0]

OK, on a donc la méthode :
Tout impair non premier étant le produit de deux impairs, donc de la forme (2x+1)(2z+1), si on prend pour 2x+1 le plus petit facteur premier, z est supérieur ou égal à x et on l'écrit x+y où y est supérieur ou égal à 0.
On fait donc la liste des (2x+1)(2x+2y+1) = 4x² + 4x + 1 + 4xy + 2y, puis on compare successivement tous les impairs à partir de 3 aux termes de la liste; s'ils n'y sont pas, ils sont premiers.
Comme ce n'est pas une méthode très utile, je n'ai pas de référence, mais depuis 2400 ans qu'on s'intéresse aux nombres premiers, elle n'est pas nouvelle (qui publierait ça ?).
En effet, quand on travaillait à la main, le crible d’Ératosthène est bien plus pratique, et quand on a commencé à programmer, fabriquer un gros tableau de "non premiers" prenait trop de place en mémoire. On utilise maintenant plutôt des tests de primalité rapides appliqués aux nombres de la forme , et on a rarement besoin de listes de petits nombres premiers.

Donc tu as trouvé une idée intéressante, utilisable pour un exercice de terminale spécialité maths (*), et c'est bien "une façon autre de rechercher" la liste des premiers nombres premiers. Encore bravo !
Par contre, c'est inutilisable pour tester si un nombre de 200 chiffres décimaux est premier ou nom, voire même pour lister les premiers entre 250 et 251 milliards.

Cordialement.

NB : Je n'avais pas testé ton programme, je suis matheux, pas informaticien. En plus, tu n'avais même pas dit quel langage tu utilisais ...

[pm42]

C'est du Eratosthene et ses très nombreuses variantes)

C'est aussi l'impression que j'ai mais j'ai du mal avec le code non formatté. Mais si c'est du Erathostène, je n'ai pas vu où on retire les multiples.

J'ai l'impression qu'il remplit son tableau de 1 avec les valeurs de x et y en pariant sur le fait que ça donne effectivement tous les impairs non premiers puis il parcourt le tableau et prend les 0 en disant que c'est des premiers.

EDIT : croisement avec gg0.

[Deedee81]

Salut,

En plus, tu n'avais même pas dit quel langage tu utilisais ...

En fait si on est informaticien, ça se voit tout de suite (c'est du C) mais bon, ce n'est pas le sujet (ni le bon forum)

[Porte7]

Rebonjour
Merci à gg0 dont la reponse est tres satisfaisante.
Et d’autant plus qu’il s’est montré très courtois.
J’ai procédé différemment selon mes moyens, mais bon je n’en parlerai pas.
Cdlt

[Porte7]

Suite.....

[Porte7]

Suite correctif tableau des X

[Deedee81]

Salut,

Heu.... quel est l'intérêt de ce tableau ???
(je ne dis pas qu'il est sans intérêt mais juste que je ne vois pas du tout à quoi ça sert, tu devrais mettre une ou deux phrases pour l'expliquer)

[gg0]

(2x+1+y)²-y² est encore une autre façon d'écrire (2x+1)(2x+2y+1). Par rapport à la formule 4x² + 4x + 1 + 4xy + 2y on gagne du temps de calcul, mais comme le problème principal est la constitution du tableau, qui prend du temps et beaucoup de mémoire, c'est une amélioration à la marge.

Au fait, Porte7, sais-tu démontrer que ça donne tous les impairs composés et chacun une seule fois seulement ?

[Porte7]

Salut gg0
Non je ne sais pas.
Je peux vous parler dentisterie et fabrication des prothèses puisque j’étais dentiste si vous voulez ?
Mais je ne suis en rien matheux ou physicien.
Cdlt

[gg0]

Alors tu es en train de bidouiller, tu crois seulement que ça marche parce que quelques petits essais ont fonctionné. Mais malheureusement un programme peut fonctionner pour de petits nombres et devenir faux ensuite. Tu n'es pas le premier à s'y laisser prendre (va voir "Nombres de Fermat" sur Internet).
Pour faire cette preuve, pas besoin d'être matheux, les maths que tu as vues en collège et lycée suffisent. Et la physique n'a rien à voir ici. Donc fais-la, sinon toi-même n'a aucune raison de proposer cet algorithme.

Cordialement.

[Deedee81]

C'est en effet la bonne manière de procéder (pas que pour les nombres premiers) :

0) facultatif mais faire "joujou" avec les nombres peut aider à éclaircir les idées, mais ça doit s'arrêter là : ce n'est ni des maths ni de l'informatique ni pédagogique.
1) D'abord une approche mathématique : purement mathématique. Ici c'est en effet assez simple (pour d'autres choses ça peut être très pointu). Inutile d'aller plus loin si c'est pas bon.
2) Une implémentation numérique/informatique : et là on peut optimiser et tout ça

J'ai eut peu à le faire (je suis dans l'informatique de gestion). Mais c'est arrivé (algorithme d'optimisation, algorithme de répartition complexe....)
Et sans le (1) : on se casse la gueule dans les grandes largeurs.
En informatique cela s'appelle : l'analyse fonctionnelle

[Porte7]

J’y suis déjà allé. Merci pour l’info.
J’ai fait de la prose sans le savoir ������ et j’ai vu que ça avait un petit lien.

[Porte7]

Une façon autre de procéder
Les démonstrations mathématiques ont été faites sur un autre forum gentiment avec un "heureux de t’avoir rendu service".
Je vais désormais bidouiller ailleurs.
Merci pour le service rendu.
Bonnes Pâques.

[pm42]

Les démonstrations mathématiques ont été faites sur un autre forum gentiment avec un "heureux de t’avoir rendu service".

gg0 les a faites ici il y a quelques jours mais tu as choisi de les ignorer.

Je vais désormais bidouiller ailleurs.

C'est le moment où on est supposer fondre en larme parce qu'on se rend compte de ce qu'on a raté, que tu as trouvé une méthode pour générer les nombres 1ers moins efficace que ce qui est connu depuis 2000 ans et te présenter nos excuses en te suppliant de revenir ?

Parce que le 1er avril, c'est demain

[albanxiii]

Si on résume, on a eu du code qui fait saigner les yeux, et ... je viens de relire le fil... rien d'autre, si on retire le hors sujet.

Au revoir Porte7, ravi que vous ayez trouvé des oreilles attentives ailleurs.

[gg0]

Porte7 : "Les démonstrations mathématiques ont été faites sur un autre forum"
Je les ai données ici, et ensuite je n'ai fait que te faire confirmer ton incompétence ("Non je ne sais pas." à propos de mathématiques de fin de collège déjà presque rédigées).

Finalement, tu n'es capable ni de justifier ta méthode, ni de tester si ta méthode est efficace, tu es juste capable de demander aux autres de le faire ... La discussion aurait dû s'arrêter après mon message #7. Où j'ai voulu être sympa ... dois-je le regretter ?