ACM 数论质因数分解

Description

Tomorrow is contest day, Are you all ready?
We have been training for 45 days, and all guys must be tired.But , you are so lucky comparing with many excellent boys who have no chance to attend the Province-Final.

Now, your task is relaxing yourself and making the last practice. I guess that at least there are 2 problems which are easier than this problem.
what does this problem describe?
Give you a positive integer, please split it to some prime numbers, and you can got it through sample input and sample output.

Input

Input file contains multiple test case, each case consists of a positive integer n(1<n<65536), one per line. a negative terminates the input, and it should not to be processed.

Output

For each test case you should output its factor as sample output (prime factor must come forth ascending ), there is a blank line between outputs.

Sample Input

-1

Sample Output

Case 1. 2 2 3 1 5 1

Case 2. 2 2 3 1

Hint

 60=2^2*3^1*5^1 
解题思路：
题目大意是给定一个数，让我们将这个数进行因式分解，然后分别输出它的质因子后面紧跟着的是这个质因子的个数，同时要求它的质因子是按从小到大的顺序输出的。格式要求，每一组测试案例之间要输出一个空行，数据输出时要求每输出一个数字就要给一个空格（注意最后一个数字输出时也要给出一个空格）。我觉得这个题目重点是让我们判断素数和累加每一个质因子的个数（我们用一个a数组来累加不同的质因子的个数，其中这个数组中元素的在下标就是这个质因子，每一个元素的值就是这个质因子的个数，记住对于每一组案例我们都要将a数组重新清0）.
程序代码：

#include <iostream>
#include <cstring>
using namespace std;
int a[65540];
int fun(int c)//判断是不是素数，是就返回1，不是就返回0
{
    if(c==2)
        return 1;
    for(int i=2;i*i<=c;i++)
    {
        if(c%i==0)
        {
            return 0;
            break;
        }
    }
    return 1;
}
int main()
{
    int x,f=1;
    while(~scanf("%d", &x) && x > 0)
    {
        if(f!=1)//两个案例之间要输出一个空行
            cout<<endl;
        memset(a,0,sizeof(a));
        int i;
        int n=x;
        for(i=2;i<=x;i++)
        {
            if(fun(n))//如果素数了的情况
            {
                a[n]++;
                break;
            }
            if(fun(i)&&n%i==0)//要求是质因子
            {
                n=n/i;
                a[i]++;//累加质因子个数
                i=1;//由于i要++，所以从1开始，而且我们要求的是升序
            }
        }
        cout<<"Case "<<f++<<"."<<endl;
        for(int j=2;j<65540;j++)
            if(a[j])
                cout<<j<<" "<<a[j]<<" ";//输出最后一个数据时，还是要输出空格
        cout<<endl;
    }
    return 0;
}

ACM 数论 质因数分解

ACM 数论质因数分解