Great Common Divisor最大公约数 n1.Euclid算法   重复gcd(a,b) = gcd(a,b mod a)至b mod a等于0 ， gcd(b,0)=b, b最后的取值为a,b初值的最大公约数   2.stein算法 1.  1.如果A=0，B是最大公约数，算法结束 2.   如果B=0，A是最大公约数，算法结束 3.   设置A1 = A、B1=B和C1 = 1 4.    如果An和Bn都是偶数，则An+1 =An /2，Bn+1 =Bn /2，Cn+1 =Cn *2(乘2整数左移一位，除2整数右移一位即可) 5. 5.如果An是偶数，Bn不是偶数，则An+1 =An /2，Bn+1 =Bn ，Cn+1 =Cn (显然，2不可能为任何奇数的约数) 6.  6.如果Bn是偶数，An不是偶数，则Bn+1 =Bn /2，An+1 =An ，Cn+1 =Cn (同上J) 7.    如果An和Bn都不是偶数，则An+1 =|An -Bn|，Bn+1 =min(An,Bn)，Cn+1 =Cn 8.    n++，转4 注：、Cn为两数最大公约数     ＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝   给定两个任意正整数n和任一质数p,求将n!表示成算术基本定理的形式的时候，p的指数． count=0; while(n) {      count+=n/p;      n/=p; } cout<<count<<endl;

评论