light oj 1035 - Intelligent Factorial Factorization 素因子分解
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("\n");
}
return 0;
}
最新文章
- mysql相关文章
- 【BZOJ1251】序列终结者 Splay
- AngularJS的小知识点
- crontab 每月最后一天
- js为表格添加行和列
- 20160329javaweb之JSP -session入门
- Serif和Sans-serif字体的区别(转)
- java常用用代码
- csharp中DateTime总结
- liunx命令3
- Zookeeper的安装的配置
- Python和Java的硬盘夜话
- MyBatis源码解析(三)——Transaction事务模块
- Java实现对象的序列化
- Python记录6:函数2,函数参数
- 做好平衡有多难?谈MMO的职业设计
- [设计模式]适配器模式Adapter
- 分享:将WDCP中的PHP5.2 1.7升级到PHP 5.3的方法
- 超简单将Centos的yum源更换为国内的阿里云源
- hdu4009最小树形图