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)
