洛谷——P2043 质因子分解

落日映苍穹つ 2023-10-02 13:11 126阅读 0赞

P2043 质因子分解

题目描述

对N!进行质因子分解。

输入格式

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

输出格式

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

输入输出样例

输入 #1复制

  1. 10

输出 #1复制

  1. 2 8
  2. 3 4
  3. 5 2
  4. 7 1

说明/提示

10!=3628800=(28)*(34)*(5^2)*7

  1. #include<bits/stdc++.h>
  2. #include<algorithm>
  3. #include<cstring>
  4. using namespace std;
  5. int a[10001]={
  6.     0},n; 
  7. int main(){
  10.       cin>>n;
  11.       for(int i=2;i<=n;i++){
  13.           int i2=i;
  14.           for(int j=2;j<=i;j++)
  15.           while(i2%j==0){
  17.               a[j]++;
  18.               i2/=j;
  19.           }
  20.       }
  21.       for(int i=1;i<=10000;i++)
  22.           if(a[i]!=0)
  23.           cout<<i<<" "<<a[i]<<endl;
  24.     return 0;
  26. }

发表评论

表情：
评论列表 （有 0 条评论，126人围观）

还没有评论，来说两句吧...

相关阅读

    相关 洛谷p1164

    > P1164 小A点菜 > > 题目描述 > > uim口袋里有剩M元（M<=10000）。 > > 餐馆虽低端，但是菜品种类不少，有N种（N<=100），第i

    亦凉亦凉/ 0 赞/ 467 阅读

    相关 质因子分解

    概念：所谓质因子分解是将一个正整数n写成一个或多个质数的乘积形式。 例如：6=2\3，180=2\2\3\3\5，也可以写成指数形式，例如 180=2^2\3^2\5^1；

    男娘i男娘i/ 0 赞/ 361 阅读