洛谷 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

 

与数论硬刚到底。。。

质因数：质因数（或质因子）在数论里是指能整除给定正整数的质数。两个没有共同质因子的正整数称为互质。因为1没有质因子，1与任何正整数（包括1本身）都是互质。正整数的因数分解可将正整数表示为一连串的质因子相乘，质因子如重复可以指数表示。根据算术基本定理，任何正整数皆有独一无二的质因子分解式。只有一个质因子的正整数为质数。

举几个例子吧

6的质因数是2和3

2,4,6,8的质因数只有2

那么对于这道题来说，我们只要分解阶乘的每一位就好了（真的算完的话会炸）

完整代码

#include<bits/stdc++.h> using namespace std; const int MAXN=10005; bool vis[MAXN]; int n,a[MAXN]; void su() { vis[0]=vis[1]=1; for(int i=2;i<=n;i++) if(!vis[i]) for(int j=2;i*j<=n;j++) vis[i*j]=1; } void div(int k) { int t=k; if(!vis[k]) { a[k]++; return; } for(int i=2;i<=t;i++) { if(!vis[i]) { if(k%i==0) a[i]++,k/=i,i--; } } } int main() { cin>>n; su(); for(int i=1;i<=n;i++)div(i); for(int i=1;i<=n;i++) if(a[i]) cout<<i<<' '<<a[i]<<endl; return 0; }

参考大佬@fleetingtime 的题解

 

转载于:https://www.cnblogs.com/pcpcppc/p/9898822.html