UVa 160 Factors and Factorials：数论

UVa 160 Factors and Factorials：数论2014-07-22 synapse7 160 - Factors and Factorials

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&page=show_problem&problem=96

题目点这：http://uva.onlinejudge.org/external/1/160.pdf

思路：遍历1~n计算质因子个数即可。

你若还想再快点的话，就用[n/p]+[n/p^2]+[n/p^3]+...+1在O（log n/log p）的时间内统计出n！的质因子p的个数。（不过此题n太小，两种方法在时间上相差不大）

完整代码：

/*0.016s*/#include<cstdio>#include<cmath>#include<cstring>int prime[100], c, ans[100];bool vis[110];inline void create_prime（）{int i, j;for （i = 2; i <= 11; ++i）if （！vis[i]）{prime[c++] = i;for （j = i * i; j < 110; j += i）vis[j] = true;}for （; i < 110; ++i）if （！vis[i]）prime[c++] = i;}int main（void）{create_prime（）;int n, temp;while （scanf（"%d", &n）, n）{memset（ans, 0, sizeof（ans））;printf（"%3d！ =", n）;for （int i = 2; i <= n; i++）{temp = i;for （int j = 0; j < c && prime[j] <= i; j++）{while （temp % prime[j] == 0）{++ans[prime[j]];temp /= prime[j];}}}for （int i = 0, j = 0; prime[i] <= n; i++, j++）{if （j % 15 == 0 && j） printf（"
"）;printf（"%3d", ans[prime[i]]）;}putchar（"
"）;}return 0;}