素数、最大公约数、最下公倍数、质因数分解

2013-08-18 11:20:43

素数、最大公约数、最下公倍数、质因数分解都是与素数相关的，解决了素数的问题，其他的都可以此为基础求解。

小结：

求1到n之间的素数的基本方法是通过遍历2到sqrt(n)，判断每个数是否是素数来得到，但这种方法效率很低；比较高效的解法是通过筛选法求解，如下面代码中函数GetPrimeUnderNBySieve；
最大公约数可通过GCD递归定理求解，通俗的说法就是辗转相除法，《算法导论》中有详细的说明；
最下公倍数可通过最大公约数得到，公式为：LCM(a,b) = a*b / GCD(a,b)；
质因数分解可通过质数表得到，如下面代码中函数GetPrimeFactorByPrimeTable所示；
另外，最后一种因数分解代码是最简练的，如函数Decomposition所示：

 1 void Decomposition(int nNum)
 2 {
 3     for(int i=2;i<nNum;)
 4     {
 5         if(nNum % i == 0)
 6         {
 7             nNum = nNum /i;
 8             cout<<i<<",";
 9         }
10         else
11         {
12             i++;
13         }
14     }
15     if(1<nNum)
16         cout<<nNum<<endl;
17 }

注意几点：

可以用乘法代替开方，进行循环结束的判断

i * i <= num

删选法时，筛子的下标变化可以通过相加或相乘来实现，如下：

相乘：

 1 for (primeIndex = 2;primeIndex * primeIndex < number;++primeIndex)
 2     {
 3         if (primeFlagArray[primeIndex])
 4         {
 5             for (sieveIndex = 2;sieveIndex * primeIndex <= number;++sieveIndex) //sieveIndex * primeIndex <= number
 6             {
 7                 primeFlagArray[sieveIndex * primeIndex] = false;
 8             }
 9         }
10     }

相加：

 1 for (primeIndex = 2;primeIndex * primeIndex < number;++primeIndex)
 2     {
 3         if (primeFlagArray[primeIndex])
 4         {
 5             for (sieveIndex = primeIndex + primeIndex;sieveIndex <= number;sieveIndex += primeIndex) //sieveIndex * primeIndex <= number
 6             {
 7                 primeFlagArray[sieveIndex] = false;
 8             }
 9         }
10     }

代码（包含测试，暂时没有发现错误，欢迎交流指正！）：

  1 #include <iostream>
  2 #include <cassert>
  3 #include <cmath>
  4 using namespace std;
  5 
  6 
  7 //显示数组元素
  8 void DisplayArray(size_t *array,size_t len)
  9 {
 10     assert(array != NULL);
 11     for (size_t index = 0;index < len;++index)
 12     {
 13         cout<<array[index]<<"	";
 14     }
 15     cout<<endl;
 16 }
 17 
 18 //判断一个数是否为质数
 19 bool IsPrime_basic(size_t num)
 20 {
 21     assert(num >= 2);
 22     for (size_t i = 2;i < num;++i)
 23     {
 24         if (num % i == 0)
 25         {
 26             return false;
 27         }
 28     }
 29     return true;
 30 }
 31 
 32 //判断一个数是否为质数
 33 bool IsPrime_improve(size_t num)
 34 {
 35     assert(num >= 2); 
 36     //for (size_t i = 2;i < sqrt(num);++i) // ambiguous call to overloaded function
 37     for (size_t i = 2;i < (int)sqrt((double)num);++i)
 38     {
 39         if (num % i == 0)
 40         {
 41             return false;
 42         }
 43     }
 44     return true;
 45 }
 46 
 47 //判断一个数是否为质数
 48 bool IsPrime(size_t num)
 49 {
 50     assert(num >= 2);
 51     for (size_t i = 2;i * i <= num;++i)  //i * i <= num而非i * i < num
 52     {
 53         if (num % i == 0)
 54         {
 55             return false;
 56         }
 57     }
 58     return true;
 59 }
 60 
 61 //用筛选法求素数
 62 size_t GetPrimeUnderNBySieve(size_t number,size_t *primeArray)
 63 {
 64     assert(primeArray != NULL);
 65 
 66     size_t primeIndex = 0;
 67     size_t sieveIndex = 0;
 68     size_t primeCounter = 0;
 69     bool *primeFlagArray = new bool[number + 1];//number + 1
 70     size_t index;
 71 
 72     for (index = 2;index <= number;++index)  //index从2开始，而非从0开始；index <= number，而非index < number
 73     { 
 74         primeFlagArray[index] = true;
 75     }
 76 
 77     //memset(primeFlagArray,1,sizeof(bool) * number);
 78 
 79     for (primeIndex = 2;primeIndex * primeIndex < number;++primeIndex)
 80     {
 81         if (primeFlagArray[primeIndex])
 82         {
 83             for (sieveIndex = 2;sieveIndex * primeIndex <= number;++sieveIndex) //sieveIndex * primeIndex <= number
 84             {
 85                 primeFlagArray[sieveIndex * primeIndex] = false;
 86             }
 87         }
 88     }
 89 
 90     for (index = 2;index <= number;++index)    //index <= number
 91     {
 92         if (primeFlagArray[index])
 93         {
 94             primeArray[primeCounter++] = index;
 95         }
 96     }
 97     delete [] primeFlagArray;
 98     return primeCounter;
 99 }
100 
101 //用筛选法求素数
102 size_t GetPrimeUnderNBySieve_2(size_t number,size_t *primeArray)
103 {
104     assert(primeArray != NULL);
105 
106     size_t primeIndex = 0;
107     size_t sieveIndex = 0;
108     size_t primeCounter = 0;
109     bool *primeFlagArray = new bool[number + 1];//number + 1
110     size_t index;
111 
112     for (index = 2;index <= number;++index)  //index从2开始，而非从0开始；index <= number，而非index < number
113     { 
114         primeFlagArray[index] = true;
115     }
116 
117     //memset(primeFlagArray,1,sizeof(bool) * number);
118 
119     for (primeIndex = 2;primeIndex * primeIndex < number;++primeIndex)
120     {
121         if (primeFlagArray[primeIndex])
122         {
123             for (sieveIndex = primeIndex + primeIndex;sieveIndex <= number;sieveIndex += primeIndex) //sieveIndex * primeIndex <= number
124             {
125                 primeFlagArray[sieveIndex] = false;
126             }
127         }
128     }
129 
130     for (index = 2;index <= number;++index)    //index <= number
131     {
132         if (primeFlagArray[index])
133         {
134             primeArray[primeCounter++] = index;
135         }
136     }
137     delete [] primeFlagArray;
138     return primeCounter;
139 }
140 
141 //用递归法求GCD
142 size_t GetGCDByRecursion(size_t a,size_t b)
143 {
144     if (b ==0)
145     {
146         return a;
147     }
148     
149     return GetGCDByRecursion(b,a % b);
150 }
151 
152 //用循环求GCD
153 size_t GetGCDByIteration(size_t a,size_t b)
154 {
155     size_t aTmp = 0;
156     while (b != 0)
157     {
158         aTmp = a;
159         a = b;
160         b = aTmp % b;
161     }
162 
163     return a;
164 }
165 
166 //用GCD求LCM，LCM(a,b) = a*b / GCD(a,b) 
167 size_t GetLCM(size_t a,size_t b)
168 {
169     return ( (a * b) / GetGCDByRecursion(a,b) );
170 }
171 
172 //求一个质数的下一个质数
173 size_t GetNextPrime(size_t currentPrime)
174 {
175     int curNum = currentPrime + 1;
176     while ( !IsPrime(curNum) )
177     {
178         ++curNum;
179     }
180     return curNum;
181 }
182 
183 //根据质数表求质因数分解
184 void GetPrimeFactorByPrimeTable(size_t num,size_t *primerFactor,size_t *pCnt)
185 {
186     *pCnt = 0;
187     if ( IsPrime(num))
188     {
189         primerFactor[(*pCnt)++] = num;
190         return;
191     }
192 
193     size_t *primeArray = new size_t[num];
194     size_t primeCounter = 0;
195     primeCounter = GetPrimeUnderNBySieve_2(num,primeArray);
196 
197     cout<<"the number of primes under "<<num<<" is :"<<primeCounter<<",they are :"<<endl;
198     DisplayArray(primeArray,primeCounter);
199 
200     assert(primeCounter <= num);
201     size_t index = 0;
202 
203     //for (index = 2;index * index < num;++index)
204     //while (index < primeCounter)
205     while (primeArray[index] <= num)
206     {
207         if (num % primeArray[index] == 0)
208         {
209             primerFactor[(*pCnt)++] = primeArray[index];
210             num = num / primeArray[index];
211             index = 0;
212 
213             //if ( IsPrime(num))
214             //{
215             //    primerFactor[(*pCnt)++] = num;
216             //    return;
217             //}
218         }
219         else
220         {
221             ++index;
222         }
223     }
224 
225     delete [] primeArray;
226 }
227 
228 //质数为自然数，所以此处的输入num为不小于最小质数2的自然数
229 //输入参数：num，待处理数字
230 //    primerFactor，存放num的质因数的数组的首地址
231 //    pCnt，存放数组长度的空间的地址
232 void GetPrimeFactor(size_t num,size_t *primerFactor,size_t *pCnt)
233 {
234     assert(num >= 2);
235     *pCnt = 0;
236     const size_t MinPrime = 2;
237     size_t currentPrime = 0;
238     while ( !IsPrime(num)  )
239     {
240         currentPrime = MinPrime;
241         while (num > currentPrime )  //num 不可能等于 currentPrime ，因为有外层while条件的保证
242         {
243             if (num % currentPrime == 0)  //从最小的质数开始，判断是否为num的因数，若不是判断下一个质数
244             {
245                 primerFactor[(*pCnt)++] = currentPrime;
246                 num = num / currentPrime;
247                 break;
248             }
249             else
250             {
251                 currentPrime = GetNextPrime(currentPrime);  //求当前质数的下一个质数
252             }
253         }
254     }
255     primerFactor[(*pCnt)++] = num;  //写入最后一个质因数
256 }
257 
258 //直接求质因数分解
259 void Decomposition(int nNum)
260 {
261     for(int i=2;i<nNum;)
262     {
263         if(nNum % i == 0)
264         {
265             nNum = nNum /i;
266             cout<<i<<",";
267         }
268         else
269         {
270             i++;
271         }
272     }
273     if(1<nNum)
274         cout<<nNum<<endl;
275 }
276 
277 //测试
278 void TestGetPrimeUnderN()
279 {
280     size_t number = 0;
281     size_t *primeArray = NULL;
282     size_t primeCounter = 0;
283     cout<<"TestGetPrimeUnderN..."<<endl;
284     cout<<"please enter a number(end with ctrl + z)"<<endl;
285     while (cin>>number)
286     {
287         primeArray = new size_t[number];
288         //primeCounter = GetPrimeUnderNBySieve(number,primeArray);
289         primeCounter = GetPrimeUnderNBySieve_2(number,primeArray);
290         cout<<"the number of primes under "<<number<<" is :"<<primeCounter<<",they are :"<<endl;
291         DisplayArray(primeArray,primeCounter);
292         cout<<"please enter a number(end with ctrl + z)"<<endl;
293         delete [] primeArray;
294     }
295 }
296 
297 void TestGetGCDAndLCM()
298 {
299     size_t a = 0;
300     size_t b = 0;
301 
302     
303     cout<<"TestGetGCD..."<<endl;
304     cout<<"please enter two numbers(end with ctrl + z)"<<endl;
305     while (cin>>a>>b)
306     {
307         cout<<"(GetGCDByRecursion)the GCD of "<<a<<" and "<<b<<" is : "<<GetGCDByRecursion(a,b)<<endl;
308         cout<<"(GetGCDByIteration)the GCD of "<<a<<" and "<<b<<" is : "<<GetGCDByIteration(a,b)<<endl;
309         cout<<"the LCM of "<<a<<" and "<<b<<" is : "<<GetLCM(a,b)<<endl;
310         cout<<"please enter two numbers(end with ctrl + z)"<<endl;
311     }
312 }
313 
314 //测试代码
315 void TestDriverGetPrimeFactor()
316 {
317     const size_t MaxNumberOfPrimeFactor = 100;
318     size_t primerFactor[MaxNumberOfPrimeFactor];
319     size_t Cnt = 0;
320     //size_t *pCnt = &Cnt;   //不能不定义Cnt，而直接用*pCnt
321     size_t num;
322 
323     cout<<"please enter a number(end with ctrl + z)"<<endl;
324     while (cin>>num)
325     {
326         //GetPrimeFactor(num,primerFactor,pCnt );
327         GetPrimeFactorByPrimeTable(num,primerFactor,&Cnt);
328         cout<<"the prime factor of number "<<num<<" is :"<<endl;
329         DisplayArray(primerFactor,Cnt);
330 
331         Decomposition(num);
332         cout<<"please enter a number(end with ctrl + z)"<<endl;
333     }
334 }
335 
336 //main
337 int main()
338 {
339     TestDriverGetPrimeFactor();
340     //TestGetPrimeUnderN();
341     //TestGetGCD();
342     return 0;
343 }