1
2 #include <NTL/FacVec.h>
3 #include <NTL/ZZ.h>
4
5
6 NTL_START_IMPL
7
8
9 static
swap(IntFactor & x,IntFactor & y)10 void swap(IntFactor& x, IntFactor& y)
11 {
12 IntFactor t;
13
14 t = x; x = y; y = t;
15 }
16
17 static
FindMin(FacVec & v,long lo,long hi)18 void FindMin(FacVec& v, long lo, long hi)
19 {
20 long minv = 0;
21 long minp = -1;
22 long i;
23
24 for (i = lo; i <= hi; i++) {
25 if (minv == 0 || v[i].val < minv) {
26 minv = v[i].val;
27 minp = i;
28 }
29 }
30
31 swap(v[lo], v[minp]);
32 }
33
34
FactorInt(FacVec & fvec,long n)35 void FactorInt(FacVec& fvec, long n)
36 {
37 if (n <= 1) LogicError("internal error: FactorInt(FacVec,long n) with n<=1");
38
39 if (NTL_OVERFLOW(n, 1, 0))
40 ResourceError("internal error: FactorInt(FacVec,long n) with n too large");
41
42 long NumFactors;
43 long q;
44
45 fvec.SetLength(2*NextPowerOfTwo(n));
46
47 NumFactors = 0;
48 q = 2;
49
50 while (n != 1) {
51 if (n%q == 0) {
52 fvec[NumFactors].q = q;
53 n = n/q;
54 fvec[NumFactors].a = 1;
55 fvec[NumFactors].val = q;
56 while (n%q == 0) {
57 n = n/q;
58 (fvec[NumFactors].a)++;
59 fvec[NumFactors].val *= q;
60 }
61 fvec[NumFactors].link = -1;
62 NumFactors++;
63 }
64
65 q++;
66 }
67
68 fvec.SetLength(2*NumFactors-1);
69
70 long lo = 0;
71 long hi = NumFactors - 1;
72
73 while (lo < hi) {
74 FindMin(fvec, lo, hi);
75 FindMin(fvec, lo+1, hi);
76 hi++;
77 fvec[hi].link = lo;
78 fvec[hi].val = fvec[lo].val * fvec[lo+1].val;
79 lo += 2;
80 }
81 }
82
83
84
85 NTL_END_IMPL
86