Voilà le code me permettant de verifier la primalité d'un nombre
EDIT: simple inversion de variables, ainsi je faisait appel a une case inexistante.
Code : Sélectionner tout - Visualiser dans une fenêtre à part
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";} }
le code ci-dessus est correct quasiment quel que soit a. (exception faite des menteurs de Fermat)
Partager