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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
|
{ GetDivisors requirement ----- START }
procedure IDivMod(const Dividend, Divisor: Longint; var Result, Remainder: Longint); register;
asm
push ebx;
mov ebx, edx;
cdq;
idiv ebx;
mov ebx, Remainder;
mov [ecx],eax;
mov [ebx],edx;
pop ebx;
end;
type
pLongintArray = ^TLongintArray;
TLongintArray = array[0..3999] of Longint;
{ il n'existe logiquement pas de nombre entier signé 32bits capable de remplir ce tableau
theoriquement un nombre qui en serait capable devrait être superieur à 2 milliard.
}
{ GetDivisors requirement ----- END }
{ GetDivisors
Renvois les diviseurs existant pour un nombre donné et precise si ce nombre
est un nombre premier ou pas.
parametres :
Number [I] longint, le nombre duquel on veut les diviseurs
pDivisors [I] pLongintArray, pointeur sur un tableau de type TLongintArray
DivisorsCount [O] longint, nombre de diviseurs trouvé et stocké dans pDivisors
AsPrime [O] boolean, true si Number est un nombre premier sinon false
}
procedure GetDivisors(const Number: Longint; const pDivisors: pLongintArray; out DivisorsCount: Longint; out AsPrime: boolean);
var DivisorA, DivisorB, Modulo : Longint;
begin
// init
AsPrime := false; // puisque les nombres premiers sont plus rare que les autres
DivisorA := 1; // le premier "plus petit diviseur" connus de Number
DivisorB := Number; // le premier "plus grand diviseur" connus de Number
Modulo := 0; // tout nombres % 1 = 0
DivisorsCount := 0; // aucuns pour l'instant
while DivisorA <= DivisorB do
{ tant que DivisorA inferieur ou egal à DivisorB, cette condition nous permet
de sortir trés rapidement de la boucle en ne testant que ce qu'il faut pour
trouver tout les diviseurs de Number.
* exemple d'iteration avec Number = 10 :
iterations | diviseurs trouvés | DivisorA | DivisorB | valides | sortie
1 | 1, 10 | 1 | 10 | oui | non
2 | 1, 10, 2, 5 | 2 | 5 | oui | non
3 | 1, 10, 2, 5 | 3 | 3 | non | oui (while a <= B)
* exemple d'iteration avec Number = 11 (nombre premier) :
iterations | diviseurs trouvés | DivisorA | DivisorB | valides | sortie
1 | 1, 11 | 1 | 11 | oui | non
2 | 1, 11 | 2 | 5 | non | non
3 | 1, 11 | 3 | 3 | non | oui (while a <= b )
* exemple d'iteration avec Number = 25 :
iterations | diviseurs trouvés | DivisorA | DivisorB | valides | sortie
1 | 1, 25 | 1 | 25 | oui | non
2 | 1, 25 | 2 | 12 | non | non
3 | 1, 25 | 3 | 8 | non | non
4 | 1, 25 | 4 | 6 | non | non
5 | 1, 25, 5 | 5 | 5 | oui | oui (if a >= b)
}
begin
{ modulo = 0 : si on a un diviseur valide sous la mains ...
}
if Modulo = 0 then
begin
{ on stocke DivisorA
}
pDivisors^[DivisorsCount] := DivisorA;
{ on incremente le compteur d'entrées, pas de inc pour eviter un call lent et inutile
le compilo vas directement nous generer une belle incrementation rapide en assembleur :)
* Comme BruNews a pus me le demontrer, en C ces deux lignes pourrait etre beaucoup plus simple
si Delphi possedait l'operateur ++ et -- ce qui serait le minimum quand même! (>_<) *
}
DivisorsCount := DivisorsCount + 1;
{ test si DivisorA est superieur ou egal à DivisorB, permet la sortie prematurée
de la boucle pour :
1) ne pas stocker DivisorB car deja present dans pDivisors (grace aux valeurs
precedentes de DivisorA)
2) eviter des appels, calculs et jump conditionnel inutiles puisqu'on sait que si
on arrive ici il ne nous reste plus qu'à determiner si Number est un nombre premier.
donc pas besoin d'aller au test DivisorA <= DivisorB, l'un ne peu fonctionner sans
l'autre pour garder des performances irreprochable dans tout les cas de figure.
}
if DivisorA >= DivisorB then
Break;
{ Stocke DivisorB puisque apparement il est toujours superieur à DivisorB
}
pDivisors^[DivisorsCount] := DivisorB;
DivisorsCount := DivisorsCount + 1;
end;
DivisorA := DivisorA + 1;
{ HAHA! une astuce de phoque, on calcul directement la division et le modulo
grace aux fonctions de l'unité ExtMath!
ça nous permet de diviser le temps et les cycles pris par la fonction par 2,
à l'instar de la fonction SinCos dans les calculs de courbes par exemple...
}
IDivMod(Number, DivisorA, DivisorB, Modulo);
end;
{ il nous reste plus grand chose à faire pour determiner que Number est un nombre premier
rappel :
un nombre premier est un nombre qui ne peut etre divisé que par 1 et par lui même.
nombre premier de 1 a 100 :
2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97.
}
AsPrime := (DivisorsCount = 2) and ((pDivisors^[0] = 1) and (pDivisors^[1] = Number));
end; |
