[问题描述]1*2*3*...*1000末尾有多说个连续的0?
1*2*3*...*1000是一个很大的数,这个数的末尾有多说个连续的0?
/*****************************************/
/**
* 算法描述(此程序未用BigInteger实现):
* 分解质因数,即:
* 1*2*3*...*1000 = (2*5)*(2*5)*...*(2*5)
*(没有匹配的2或5) //其实地球人都知道2肯定比5多
//这样其实只需要确定因子5的个数即可
*(除2和5以外的其他质因数)
* 其因子中有多少个(2*5)即末尾有多少个0
* 因此问题变成求每个数中2和5因子的个数,再求和
* 最后min(因子2个数的总和,因子5个数的总和)即是所求。
*/
public class SumZero {
SumZero(){
max = 1000;//默认值是1000
}
SumZero(int n){
max = n;//可以通过构造函数修改max的值
}
private int max;
/**
* 得到max的因子 m 的个数
*/
public int getFactor(int m){
int count = 0,
n = max;
//try 中的便是程序的核心
try{
while(n%m == 0){//能被m整除则count++
count++;
if(n >= m){
n /= m;
}
}
}
catch(Exception e){
e.printStackTrace();
}
return count;
}
/**
* 得到末尾0的个数
*/
public int getNumber(){
int count_2 = 0,//因子2的个数
count_5 = 0;//因子5的个数
for(int i = 1;i<=max;i++){
count_2 += getFactor(i,2);//其实没有必要求因子2的个数
count_5 += getFactor(i,5);
}
return Math.min(count_2,count_5);//必定有:count_5 < count_2
}
public static void main(String[] args){
System.out.println("1*2*...*1000的末尾有"
+new SumZero().getNumber()
+"个0");
}
} |