100的阶乘后面有多少个0

#include <bits/stdc++.h>

using namespace std;

bool IsPrime(int x){

if(x == 2 || x == 3)

return true;

if(x % 6 != 1 && x % 6 != 5)

return false;

int x_sqrt = (int)sqrt(x);

for(auto i = 5;i <= x_sqrt;i+=6){

if(x % i == 0 || x % (i+2) == 0)

return false;

}

return true;

}

int GetNextFactor(int factor){

if(factor == 2)

return 3;

int f;

for(f = factor + 2;true;f += 2){

if(IsPrime(f))

return f;

}

return -1;

}

/*因式分解*/

void func(int x,map<int,int> &ret){

int factor = 2;

while(x != 1){

if(x % factor == 0){

++ret[factor];

x /= factor;

}

else{

factor = GetNextFactor(factor);

}

}

}

int main(){

int n;

while(cin >> n){

/*因式分解后2的个数和5的个数*/

int num2 = 0,num5 = 0;

map<int,int> ret;

for(auto i = 2;i <= n;++i){

ret.clear();

func(i,ret);

for(auto it = ret.begin();it != ret.end();++it){

if(it->first == 2)

num2 += ret[it->first];

if(it->first == 5)

num5 += ret[it->first];

}

}

cout<<min(num2,num5)<<endl;

}

return 0;

}

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容