Given an integer N, you have to prime factorize N! (factorial N).
Input
Input starts with an integer T (≤ 125), denoting the number of test cases.
Each case contains an integer N (2 ≤ N ≤ 100).
Output
For each case, print the case number and the factorization of the factorial in the following format as given in samples.
Case x: N = p1 (power of p1) * p2 (power of p2) * ...
Here x is the case number, p1, p2 ... are primes in ascending order.
Sample Input |
Output for Sample Input |
3 2 3 6 |
Case 1: 2 = 2 (1) Case 2: 3 = 2 (1) * 3 (1) Case 3: 6 = 2 (4) * 3 (2) * 5 (1) |
Notes
The output for the 3rd case is (if we replace space with '.') is
Case.3:.6.=.2.(4).*.3.(2).*.5.(1)
代码:
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define N 200
using namespace std;
int n, k, id;
int a[N], b[N], prime[N], vis[N];
void init()///素数表
{
for(int i = 2; i < N; i++)
{
if(!vis[i])
{
prime[k++] = i;
for(int j = i + i; j < N; j += i)
vis[j] = 1;
}
}
}
void input(int n)
{
id = 0;
memset(a, 0, sizeof(a));
memset(b, 0, sizeof(b));
for(int i = n; i >= 1; i--)
{
int tmp = i, t;
for(int j = 0; j < k && prime[j] <= n; j++)
{
t = 0;
while( tmp % prime[j] == 0)
{
t++;
tmp /= prime[j];
}
if(t != 0)
{
if(a[prime[j]] == 0)///如果该素数没有出现过,就把他放入数组b中。
b[id++] = prime[j];
a[prime[j]] += t;///把素数的个数存在a数组中。
}
}
}
}
void deal()
{
printf("%d = ", n);
sort(b, b+id);
for(int i = 0; i < id; i++)
{
if(i == 0)
printf("%d (%d)", b[i], a[b[i]]);
else
printf(" * %d (%d)", b[i], a[b[i]]);
}
}
int main(void)
{
int T, cas;
init();
scanf("%d", &T);
cas = 0;
while(T--)
{
cas++;
scanf("%d", &n);
input(n);
printf("Case %d: ", cas);
deal();
printf("
");
}
return 0;
}