P2043 质因子分解

题目描述

对  N! 进行质因子分解。

输入格式

输入数据仅有一行包含一个正整数  N， N≤10000。

输出格式

输出数据包含若干行，每行两个正整数  p,a，中间用一个空格隔开。表示  N! 包含 a 个质因子  p，要求按  p 的值从小到大输出。

输入输出样例

输入 #1

 10

输出 #1

2 8

3 4

5 2

7 1

说明/提示

10 ! = 3628800 = ( 2^8 ) × ( 3^4 ) × ( 5^2 ) × 7 。

代码

#include<iostream> 
#include <algorithm>
using namespace std;
int b[10004];//用数组来存放前n个数的质因数
int main(){int n;cin>>n;for(int i=2;i<=n;i++){int p=i;while(p>1){//前n个数的约数不能小于等于1for(int j=2;j<=i;j++){//每次寻找最小能整出的数if(p%j==0){b[j]++;//将质因数加起来p/=j;break;}}}
}for(int i=1;i<=n;i++){//输出if(b[i]!=0){cout<<i<<" "<<b[i]<<"\n";}}return 0;
}