Steven5538

大數因式分解

Word count: 1.7kReading time: 9 min
2011/12/05 Share

一樣是學校的作業題目,整個花了很多時間..
輸出則是輸出到文件output.txt。
大數分解基本上最快應該是用質因數分解,不過本人實力有限,我一直想不出要怎麼把質因數乘成所有因數。
原始碼有點複雜,先附上完整原始碼,然後再分開來解釋一下。

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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
#include <iostream>
#include <fstream>
#include <ctime>
#define SIZE 500

using namespace std ;

bool BigSub (int LengthA , int *BigA , int *BigB , int *BigSum) ;
int DivisorAdd (int LengthA , int count , int *BigA , int *BigB , int *BigSum , int BigNumber[][SIZE]) ;
int BigDiv (int LengthA , int count , int *BigA , int *BigB , int *BigSum , int BigNumber[][SIZE]) ;
void CoutBig (int count , int BigNumber[][SIZE]) ;

int main ()
{
clock_t start , end ;
float total ;
char cin_BigA[SIZE] ;
bool flag = false ;
ofstream Tables ;
int BigA[SIZE] = {0} , BigB[SIZE] = {0} , BigSum[SIZE] = {0} , BigNumber[SIZE][SIZE] = {0} , LengthA , count = 0 ;

cout << "Enter a positive integer: " ;
cin.getline (cin_BigA , SIZE) ;

Tables.open ("output.txt" , ios::out) ;
if (!Tables.is_open())
cout << "Error!" << endl ;
else
Tables << "All proper factors of " << cin_BigA << ":" << endl << endl ;

strrev (cin_BigA) ;
LengthA = strlen(cin_BigA) ;
for (int i = 0 ; i < LengthA ; i++) //get BigNumber
BigA[i] = cin_BigA[i] - 48 ;

for (int i = SIZE - 1 ; i >= 0 ; i--)
BigSum[i] = BigA[i] ;

start = clock() ;
while (1)
{
for (int i = SIZE - 1 ; i >= 0 ; i--) // first check if Sum < B
{
if (BigSum[i] > BigB[i])
{
flag = true ;
break ;
}
if (BigSum[i] < BigB[i])
flag = false ;
}

if (flag == true)
count = DivisorAdd (LengthA , count , BigA , BigB , BigSum , BigNumber) ; // divisor++
else
break ;
}
end = clock() ;

CoutBig (count , BigNumber) ;

total = float(end - start) / CLOCKS_PER_SEC ; //time

cout << total << " Seconds." << endl ;

system ("pause") ;
return 0 ;
}

void CoutBig (int count , int BigNumber[][SIZE]) // cout
{
int i ;
bool flag = false ;
ofstream Tables ;
Tables.open ("output.txt" , ios::app) ;
if (!Tables.is_open())
cout << "Error!" << endl ;
else
{
for (int k = 0 ; k < count ; k++)
{
if ((k + 1) % 2 != 0)
{
for (i = SIZE - 1 ; i >= 0 ; i--) // cout without 0
{
if (BigNumber[k][i] != 0)
{
flag = true ;
break ;
}
}

if (flag == true)
{
for (i ; i >= 0 ; i--)
Tables << BigNumber[k][i] ;
}
else
Tables << "0" ; // flag = flase mean only 0

Tables << endl ;
}
}

for (int k = count - 1 ; k > 1 ; k--)
{
if ((k + 1) % 2 == 0)
{
for (i = SIZE - 1 ; i >= 0 ; i--) // cout without 0
{
if (BigNumber[k][i] != 0)
{
flag = true ;
break ;
}
}

if (flag == true)
{
for (i ; i >= 0 ; i--)
Tables << BigNumber[k][i] ;
}
else
Tables << "0" ; // flag = flase mean only 0

Tables << endl ;
}
}

}
}

int DivisorAdd (int LengthA , int count , int *BigA , int *BigB , int *BigSum , int BigNumber[][SIZE]) // divisor++
{
BigB[0]++ ;
for (int i = 0 ; i < LengthA ; i++)
{
if (BigB[i] >= 10)
{
BigB[i + 1]++ ;
BigB[i] = 0 ;
}
}

count = BigDiv (LengthA , count , BigA , BigB , BigSum , BigNumber) ;

return count ;
}

bool BigSub (int LengthA , int *BigA , int *BigB , int *BigSum) // sub
{
int Borrow = 0 ; // sub number

for (int i = LengthA - 1 ; i >= 0 ; i--) // first check if A < B
{
if (BigA[i] > BigB[i])
break ;
if (BigA[i] < BigB[i])
return false ;
}

for (int i = 0 ; i < LengthA ; i++)
{
BigSum[i] = BigA[i] - BigB[i] - Borrow + 10 ; // add 10 here
if (BigSum[i] < 10) // if smaller than 10 , mean it < 0 , borrow from next number.
Borrow = 1 ;
else
{
Borrow = 0 ;
BigSum[i] -= 10 ; // bigger than 10 , so sub it.
}
}

return true ;
}

int BigDiv (int LengthA , int count , int *BigA , int *BigB , int *BigSum , int BigNumber[][SIZE]) // div
{
int i , LengthB ;
bool flag = false ;
int BigA_Tmp[SIZE] = {0} , BigB_Tmp[SIZE] = {0} , BigSum_Tmp[SIZE] = {0} ;

for (i = LengthA - 1 ; i >= 0 ; i--)
BigA_Tmp[i] = BigA[i] ;
for (i = LengthA - 1 ; i >= 0 ; i--)
BigB_Tmp[i] = BigB[i] ;
for (i = LengthA - 1 ; i >= 0 ; i--)
BigSum[i] = 0 ;

for (i = LengthA - 1 ; i >= 0 ; i--) // remove 0 to get how long is B
{
if (BigB[i] != 0)
break ;
}

LengthB = i + 1 ;

if (LengthA > LengthB) // fill the seats with 0
{
for (i = LengthB - 1 ; i >= 0 ; i--)
BigB_Tmp[i + LengthA - LengthB] = BigB_Tmp[i] ;
for (i = LengthA - LengthB - 1 ; i >= 0 ; i--)
BigB_Tmp[i] = 0 ;
}

for (i = LengthA - LengthB ; i >= 0 ; i--) // sub
{
while(1)
{
flag = BigSub (LengthA , BigA , BigB_Tmp , BigA) ;
if (flag == false)
break ;
else
BigSum_Tmp[i]++ ;
}

for (int j = 0 ; j < SIZE - 1 ; j++)
BigB_Tmp[j] = BigB_Tmp[j + 1] ;
}

for (i = LengthA - 1 ; i >= 0 ; i--)
BigSum[i] = BigSum_Tmp[i] ;

for (i = LengthA - 1 ; i >= 0 ; i--) //check if remainder = 0
{
if (BigA[i] != 0)
{
flag = false ;
break ;
}
else
flag = true ;
}

if (flag == true)
{
for (i = 0 ; i < LengthA ; i++)
BigNumber[count][i] = BigB[i] ;

count++ ;

for (i = 0 ; i < LengthA ; i++)
BigNumber[count][i] = BigSum[i] ;

count++ ;
}

for (i = LengthA - 1 ; i >= 0 ; i--) //get A back
BigA[i] = BigA_Tmp[i] ;

return count ;

}

首先這段是先檢查商數是否大於除數,大於基本上就是除完了所有因數,還沒成立就呼叫DivisorAdd。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
while (1)
{
for (int i = SIZE - 1 ; i >= 0 ; i--) // first check if Sum < B
{
if (BigSum[i] > BigB[i])
{
flag = true ;
break ;
}
if (BigSum[i] < BigB[i])
flag = false ;
}

if (flag == true)
count = DivisorAdd (LengthA , count , BigA , BigB , BigSum , BigNumber) ; // divisor++
else
break ;
}

接下來這段主要就是讓除數不斷+1,同時每次check大於10就進位,做完呼叫BigDiv。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int DivisorAdd (int LengthA , int count , int *BigA , int *BigB , int *BigSum , int BigNumber[][SIZE])  // divisor++
{
BigB[0]++ ;
for (int i = 0 ; i < LengthA ; i++)
{
if (BigB[i] >= 10)
{
BigB[i + 1]++ ;
BigB[i] = 0 ;
}
}

count = BigDiv (LengthA , count , BigA , BigB , BigSum , BigNumber) ;

return count ;
}

這段開始便是做長除法的前置,長除法本身是由減法組成,在這裡先用0補位,然後再去減,最後檢查如果有餘數則表示不整除,不是因數。這段代碼會呼叫BigSub去做大數減法。

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
int BigDiv (int LengthA , int count , int *BigA , int *BigB , int *BigSum , int BigNumber[][SIZE])  // div
{
int i , LengthB ;
bool flag = false ;
int BigA_Tmp[SIZE] = {0} , BigB_Tmp[SIZE] = {0} , BigSum_Tmp[SIZE] = {0} ;

for (i = LengthA - 1 ; i >= 0 ; i--)
BigA_Tmp[i] = BigA[i] ;
for (i = LengthA - 1 ; i >= 0 ; i--)
BigB_Tmp[i] = BigB[i] ;
for (i = LengthA - 1 ; i >= 0 ; i--)
BigSum[i] = 0 ;

for (i = LengthA - 1 ; i >= 0 ; i--) // remove 0 to get how long is B
{
if (BigB[i] != 0)
break ;
}

LengthB = i + 1 ;

if (LengthA > LengthB) // fill the seats with 0
{
for (i = LengthB - 1 ; i >= 0 ; i--)
BigB_Tmp[i + LengthA - LengthB] = BigB_Tmp[i] ;
for (i = LengthA - LengthB - 1 ; i >= 0 ; i--)
BigB_Tmp[i] = 0 ;
}

for (i = LengthA - LengthB ; i >= 0 ; i--) // sub
{
while(1)
{
flag = BigSub (LengthA , BigA , BigB_Tmp , BigA) ;
if (flag == false)
break ;
else
BigSum_Tmp[i]++ ;
}

for (int j = 0 ; j < SIZE - 1 ; j++)
BigB_Tmp[j] = BigB_Tmp[j + 1] ;
}

for (i = LengthA - 1 ; i >= 0 ; i--)
BigSum[i] = BigSum_Tmp[i] ;

for (i = LengthA - 1 ; i >= 0 ; i--) //check if remainder = 0
{
if (BigA[i] != 0)
{
flag = false ;
break ;
}
else
flag = true ;
}

if (flag == true)
{
for (i = 0 ; i < LengthA ; i++)
BigNumber[count][i] = BigB[i] ;

count++ ;

for (i = 0 ; i < LengthA ; i++)
BigNumber[count][i] = BigSum[i] ;

count++ ;
}

for (i = LengthA - 1 ; i >= 0 ; i--) //get A back
BigA[i] = BigA_Tmp[i] ;

return count ;

}

這段就是大數減法了,應該是不難理解。

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
bool BigSub (int LengthA , int *BigA , int *BigB , int *BigSum)  // sub
{
int Borrow = 0 ; // sub number

for (int i = LengthA - 1 ; i >= 0 ; i--) // first check if A < B
{
if (BigA[i] > BigB[i])
break ;
if (BigA[i] < BigB[i])
return false ;
}

for (int i = 0 ; i < LengthA ; i++)
{
BigSum[i] = BigA[i] - BigB[i] - Borrow + 10 ; // add 10 here
if (BigSum[i] < 10) // if smaller than 10 , mean it < 0 , borrow from next number.
Borrow = 1 ;
else
{
Borrow = 0 ;
BigSum[i] -= 10 ; // bigger than 10 , so sub it.
}
}

return true ;
}

整個代碼可說是挺冗長的,但這還不是最佳解,本代碼目前測過12位數最快可以到5秒多。
聽說質因數分解可以30位數秒殺…

希望有人能告訴我質因數分解的寫法:)

CATALOG