Forum Clubic

Arrêt d'un algorithme sans raison apparente [résolu]

Bonjour, je suis débutant et j’aurais voulu savoir pourquoi mon programme de recherche de nombre premiers ci dessous s’arrête au 65087eme nombre trouvé. Merci d’avance pour votre aide.

Code source :

[cpp]#include <iostream.h>

#define stop1 1000
#define stop2 100

int Decomposition();

unsigned long V;
unsigned long a;
unsigned long int res1;
unsigned long res2;
double resDouble;
unsigned long int M;
unsigned long int B;
short L1;
short L2;
short L1max;
short L2max;
unsigned long Pmax;
unsigned long compteur;
unsigned long compteur2;
unsigned long compteurV;
unsigned long tmp;

unsigned long int tabP[stop1][stop2];

int Valeurs()
{
V=9;
M=V;
cout << (sizeof tabP)/1024 << " ko";
tabP[0][0]=2;
cout << “Premier N°1 : 2”<<’\n’;
tabP[1][0]=3;
cout << “Premier N°2 : 3”<<’\n’;
tabP[2][0]=5;
cout << “Premier N°3 : 5”<<’\n’;
tabP[3][0]=7;
cout << “Premier N°4 : 7”<<’\n’;
Pmax=7;
L1=(-1);
L2=0;
compteur2=4;
B=16;
L1max=3;
}

int incrementation()
{
M=M+2;
V=M;
L1=0;
L2=0;
}

int Enregistrer()
{
compteur2++;
compteur++;
cout << “Premier N°”<<compteur2<<" : " << V <<’\n’;
if (compteur==B)
{
compteur=0;
cout << (sizeof tabP)/1024 << " ko" <<’\n’;
cin>>B;
}
/*
if (V-2==tabP[L1max])
{
cout << “JUMEAUX :”<<V <<" ; " <<tabP[Lmax] <<’\n’;
}*/
L1max++;
if (L1max==stop1)
{
L1max=0;
L2max++;
}
tabP[L1max][L2max]=V;
Pmax=V;
incrementation();
Decomposition();
}

int Decomposition()
{
while (V<4294967295)
{
L1++;
a=tabP[L1][L2];
res1=V%a;
res2=V/a;
/*
if (compteur2>65085)
{
//cout << “V :”<<V<<’\t’<< “a :”<<a<<’\t’<< “res2,res1 :”<<’\t’<<res2<<" | "<<res1<<’\t’<<’\n’;
cin >> tmp;
}
*/
if (res1==0)
{
L1=0;
L2=0;
V=res2;
}

        if (a>res2)
        Enregistrer();
        
        if (V<Pmax)
        incrementation();
        
        if ((L1-1)==stop1)
        {
           L1=0;
           L2++;
        }
  }

}

int main()
{
Valeurs();
Decomposition();
}
[/cpp]

chez moi moi ça marche.
Premier N°65088 : 815527

Que de variables globales!! :confused:

Les variables globales c’est parce que je savais pas où les caser, donc j’ai tout mis hors des fonctions. Sinon est ce que le programme plante plus loin, lorsque tu laisse le programme calculer ? Ca peut venir du compilateur ?

arf ok ton algo est recursif.
chez moi ça plante un peu plus loin.

Premier N°261999 : 1623717

Le seul moyen c’est de lineariser ton algo. (si c’est possible)

et tu peux remplacer 4294967295 par ULONG_MAX defini dans limits.h

A prioris je pense que c’est possible de virer les appels recursifs. Tu fait tout les appels dans une meme fonction et tu rajoute des valeurs de retour dans tes fonctions pour savoir quelle fonction appeller.

pour commencer tu peux sortir l’appel a decomposition dans enregistrer.
rien qu’avec ça l’algo va jusqu’a
Premier N°523993 : 2147705

Ok, merci pour ces infos, je teste tout de suite :slight_smile: .

Bon, j’arrive à plus de 230000. Juste une dernière question : d’où vient la différence entre les 2 machines ?

j’ai un giga de ram.

a prioris
dans le “if (a>res2)” tu sort jamais de l’appel a decomposition alors tu peux faire un continue pour aller a l’iteration suivante de la boucle plutot que de rappeller la fonction.

[cpp]
if (a>res2)
{
Enregistrer();
Decomposition();
cout << "si ce message ne s’affiche pas tu peux a prioris remplacer la ligne du dessus par “continue”; " << endl;
}
[/cpp]

5 millions de nombres premiers et ça tourne toujours.

Maintenant je peux pas t’aider plus. je connais pas ton algo mais il y a moyen de faire quelque chose de plus propre que ça.

Je tape comment le “continue”; " << endl; ?
Je met :

  1. continue;
  2. <<endl;
    ?
    Quand je dis débutant c’est vraiment débutant : un demi manuel C++, c tout.

De ce que je me souviens, c’est possible de virer la récursivité (d’où éviter de planter en bouffant toute la pile) soit avec le Crible d’Erasthène (là tu les auras tous) soit dans une boucle appelant ta fonction, et en utilisant un algo simple :

Si (N % 2) == 0 Retour Faux
Pour i := 3 à RacineCarre(N)
Faire
Si i divise N (N % i==0) Retour Faux
i := i + 2;
Fin.
Retour Vrai.
Tu dois même pouvoir optimiser en ajoutant de manière à virer 5 (si i == 0 [5], i += 2) vu que seul les nombres finissant par 1, 3, 7, 9 sont des nombres potentiellement premiers (sauf 2, 5 bien sûr).

lol desolé je voulais pas t’embrouiller

endl c’est juste un maniere plus propre de faire un retour a la ligne en c++;
le \ avant les " c’est juste pour que le compilo sache que c’est dans la chaiune de caractere et qu’il ne doit pas l’interpreter comme la fin de la chaine.

tu met juste continue;
l’instruction continue dans une boucle passe directement a l’iteration suivante en zeappant tout ce qui suit.

ok, merci.
Pour ton petit truc Sans-Nom, j’essairai de coder quelquechose avec cette aprem.