NYOJ 509 因子和阶乘

叁歲伎倆 2022-09-19 10:37 102阅读 0赞

## 因子和阶乘 ##

时间限制： 1000 ms | 内存限制： 65535 KB

难度： 2

描述

给你一个正整数n，把n!=1x2x3x.....xn分解成素因子相乘的形式，并从小到大输出每个素因子的指数，但要保证最后输出的素因子个数不为0。例如825应表示为0,1,2,0,1表示分别有0,1,2,0,1个2,3,5,7,11。

输入

第一行有一个整数n(0<n<10000),表示有n组测试数据；  
接下来n行每行有一个整数 m(1<m<10000)

输出

从小到大输出m分解成素因子相乘后各个素因子对应的指数

样例输入

2
    5
    53

样例输出

3 1 1
    49 23 12 8 4 4 3 2 2 1 1 1 1 1 1 1

思路：如果以前有做过将72分解为2\*2\*2\*3，那么这道题原理一样，很简单。

#include <stdio.h>
    #include <string.h>
    
    void number(int *a,int n)
    {
    	int i;
    	for (i=2; i<=n; i++)
    	{
    		if(n % i == 0)
    		{
    			a[i]++;
    			n = n/i;
    			i = 1;
    		}
    	}
    }
    
    int main()
    {
    	int m;
    	int a[10001];
    	scanf("%d",&m);
    	while (m--)
    	{
    		int i,n;
    		scanf("%d",&n);
    		memset(a,0,sizeof(a));
    		for (i=2; i<=n;i++)
    		{
    			number(a,i);
    		}
    		for (i=2; i<=n;i++)
    		{
    			if (a[i])
    			{
    				printf("%d ",a[i]);
    			}
    		}
    		printf("\n");
    	}
    	return 0;
    }

还可以利用 阶乘因素分解的思路来做

#include<stdio.h>
    #include<string.h>
    
    #define N 10005
    
    void Prime(int *a, int*b)
    {
        int i,j,k=0;
        for(i=2;i<102;i++)
            if(!a[i])
                for(j=i*i;j<N;j+=i)
                    a[j]=1;
        for(i=0;i<N;i++)
            if(!a[i])  b[k++]=i;
    }
    int acm(int n,int m){
        int k=0;
        while(n)
    	{
            n=n/m;
            k+=n;
        }
        return k;
    }
    int main()
    {
        int i,m,n;
    	int a[N]={1,1,0};
    	int b[2000];
        Prime(a,b);
        scanf("%d",&n);
        while(n--)
    	{
            scanf("%d",&m);
            for(i=0;b[i]<=m;i++)
    		{
                printf("%d ",acm(m,b[i]));
    		}
            printf("\n");
        }
    	return 0;
    }