UVa 160 Factors and Factorials：数论

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("\n      ");
            printf("%3d", ans[prime[i]]);
        }
        putchar('\n');
    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索http
， include
， uva
， 时间
， 数论
， 个数
debugc++uva
successfactors、human factors、sap successfactors、factors、prime factors，以便于您获取更多的相关知识。