Erreur : Segmentation Fault dans un test de primalité
Voilà le code me permettant de verifier la primalité d'un nombre
Code:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61
|
#include <iostream>
#include <vector>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <ctime>
#include <cmath>
using namespace std;
void Binary(int n, int& u, int& t)
{
int x(n - 1);
int i(42);
while (i==42)
{if (x % 2 == 0)
{x = x/2;
t += 1;}
else
{u = x;
i = 1;}
}
}
bool Witness(int n,int a)
{
int u(0), t(0), x;
int i(1);
vector<int> valeurs(1, 0);
Binary(n, u ,t);
cout << a << " " << t << endl;
x = pow(a,t);
cout << x << endl;
valeurs[0] = x % n;
cout << valeurs[0] << endl;
for (i = 1; i <= u; i++)
{
int x(pow(valeurs[i-1],2));
valeurs.push_back(x % n);
if (valeurs[i] == 1 && valeurs [i-1] != 1 && valeurs[i-1] != n-1)
{return true;}
}
if (valeurs[u] != 1)
return true;
else {return false;};
}
int main()
{
int n;
int a;
cout <<"entrez un entier impair et un nombre pour le tester";
cin >> n;
cin >> a;
if (Witness(n, a) == true)
{cout << "cet entier est premier";}
else {cout << "try again";}
} |
EDIT: simple inversion de variables, ainsi je faisait appel a une case inexistante.
le code ci-dessus est correct quasiment quel que soit a. (exception faite des menteurs de Fermat)