题目描述

Z 国的国王是一个非常爱好数学的国王。一天他对着他的那些大臣说：“素数真是一种神奇的正整数，除了1和它本身外，不能被其他任何正整数整除，2是最小的素数，有无穷多个啊……它还有一个美妙的名字：质数，……数学多么有趣啊……”。  
Z 国今年风调雨顺，百姓丰衣足食。为了奖励他那帮管理有方的大臣，他决定把全部的 N 元奖金平均分配给其中的 K 位大臣，但酷爱数学的国王要求这 K 位大臣每人拿到的奖金必须是个素数。哪个大臣能够解决这个数学问题，国王就把奖金给这个大臣和另外的 K-1 人。  
 大臣们都想自己获得更多的奖金，所以希望分得奖金的大臣人数 K 越少越好。机智的大臣请来了“编程大侠”来帮忙解决这个问题。国王的间谍得知了这个情况后向国王汇报了大臣的行为。国王早就听说“编程大侠”的厉害，于是决定问 T 次这个问题，来试探一下 
“编程大侠”的真正实力。

 

输入

输入共T+1行。
第1行一个整数T，表示国王问了T次。
接下来T行每行一个整数N，表示国王打算分配给大臣的总奖金。

 

输出

输出共T行。
第i行一个整数K，表示最少多少位大臣来平分输入中对应的全部奖金。如果找不到满足国王要求的分配办法，请输出“0”（输出时不包含双引号）。

国王共问了 3 次。  
第一次国王说：“我们总共有 3 元奖金”。“编程大侠”说：“最少分配给 1 位大臣，他可以获得所有奖金，即 3 元，因为 3 是一个素数”。  
第二次国王说：“我们总共有 4 元奖金”。“编程大侠”说：“最少分配给 2 位大臣，他们每人可以获得 2 元奖金，因为 2 是一个素数”。  
第三次国王说：“我们总共有 100 元奖金”。“编程大侠”说：“最少分配给 20 位大臣，他们每人可以获得 5 元奖金，因为 5 是一个素数”。

 

分析：

1.根据国王的问法与分配方法，可以肯出，可以整除的那个最大的素数。

2.根据唯一分解定理，任何一个大于1的数都可以表示出，几个连续质数的乘积。

3.所以可以将这个数 的质因数从小到大乘起来，保留他的积，最后用n除以他的积，即为最大的素数。

4.代码也增加了一个输出，输出该数的乘积表示 比如120=2*2*2*3*5，用来验证唯一分解定理。

#include <stdio.h>
#include <algorithm>
#include <string.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
int vis[(int)(1e6+5)];
int prime[(int)(1e6+5)];
int main(){

    int cnt=0;
    for(int i=2;i<=1e6;i++)
        if(!vis[i])
        {
            prime[++cnt]=i;
            for(int k=2*i;k<=1e6;k+=i)
                vis[k]=1;
        }
    int m,n;
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        int a[50000];
        int ans=0;
        m=1;
        int z=n;
        for(int i=1;i<=cnt;i++)
        {
            while(n%prime[i]==0)
            {
                n/=prime[i];
                if(n!=1)
                m*=prime[i];
                a[++ans]=prime[i];
            }
            if(n==1)
                break;
        }
       for(int i=1;i<=ans;i++)
        {
            if(i!=ans)
                printf("%d*",a[i]);
            else
                printf("%d",a[i]);
        }
        printf("\n%d\n",z==1?0:m);
    }

    return 0;
}