根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。
n=p1^a1 * p2^a2 *p3^a3.....pn^an
比如一个数16 在分解时先找到2这个质因子，然后由于16/2后还可以/2，所以会在2这个质因子上产生次方
不优化版本：从2~n 找到能整除的因子然后算次方
提前不满意这个不优化版本
这里有个性质：n中最多只含有一个大于sqrt(n)的因子。证明通过反证法：如果有两个大于sqrt(n)的因子，那么相乘会大于n，矛盾。证毕
于是我们发现最多只有一个大于sqrt(n)的因子，对其进行优化。先考虑比sqrt(n)小的，代码和质数的判定类似
最后如果n还是>1，说明这就是大于sqrt(n)的唯一质因子，输出即可。
C++
#include<iostream>
#include<algorithm>
using namespace std;
int main(void)
{
int n;cin>>n;
while(n--)
{
int a;cin>>a;
for(int i=2;i<=a/i;i++)
{
if(a%i==0)
{
int s=0;
while(a%i==0)
{
a/=i;
s++;
}
cout<<i<<" "<<s<<endl;
}
}
if(a>1) cout<<a<<' '<<1<<endl; ///
cout<<endl;
}
return 0;
}
### 这里点赞多我就在这里证明一下循环里面的
i一定是一个质数：假如i是一个合数，那么它一定可以分解成多个质因子相乘的形式，这多个质因子同时也是a的质因子且比i要小，而比i小的数在之前的循环过程中一定是被条件除完了的，所以i不可能是合数，只可能是质数说得好！
确实
雀石
orz
66
orz
感谢
Orz
orz
牛逼
orz
orz
掌声给到你！
orz
$6$
帅
说的太好了,佬nb
嗯
补充一下，合数的i是会被for循环遍历到的，但是合数的i在第一个判断if(a%i==0)就会被否掉，跳出当次循环
牛逼
orz
### 这里有个性质：n中最多只含有一个大于sqrt(n)的因子。证明通过反证法：如果有两个大于sqrt(n)的因子，那么相乘会大于n，矛盾。证毕 ###
这里说的有一点不严谨，应修改为“质因子”，举个例子，36的平方根是6，而12和18都是大于6的因子。
其实说白了，假设有因子i>sqrt(n),即n/i==0,那么它应当在i<sqrt(n)时就会被发现——因为他对应的因子n/i<sqrt(n)
唯一的落网之鱼就是其本身就是质数，如37
# 说得好 最后剩下的要么是1，要么是唯一的大于原数开方的质因子
终于明白了，感谢
我再证明一下循环里面的 i为什么 一定是一个质数：
循环从 i=2 开始，并递增到 a/i。对于每一个 i，如果 a 能被 i 整除，那么 i 就是 a 的一个因子。
但我们如何确保这个因子 i 一定是质数呢？
想象一下，如果 i 不是质数，那意味着 i 有一个小于它的质因子，记为 p（p < i）。而在我们的循环中，由于我们是从 2 递增检查的，所以在检查到 i 之前，我们已经检查过 p 了。
如果 a 能被 i 整除，且 i 有一个质因子 p，那么 a 也能被 p 整除。但是当我们在循环中首次碰到一个能整除 a 的数 p 时，我们会连续除以这个数直到 a 不再被它整除。这意味着当循环到 i 时，a 不可能还被 p 整除，因为 p 已经被完全除尽了。
因此，当我们在循环中找到 a 可以被 i 整除时，i 不可能是合数，因为它的所有小于它的质因子已经被检查过并除尽了。这就确保了 i 必须是质数。
%%%
很形象，Orz
最后剩下的数如果大于1， 并不能说明这个数一定是大于sqrt（n）的一个质因数，例如分解96的质因数，96 = 2^5 * 3，当分解完质因数2后，n已经为3，此时i不满足 i <= n / i，会进入后面一个判断，而3并不是大于sqrt（96）的数
很有道理，同问，求解答！！！！
为啥没人回这条评论？？？
可能是 n 在每次循环中会变化；
在判断之前 n=96 会一直除以因数 2 (n /= i)，结果为 n=3；3 大于 sqrt(3)；
不知道这样理解对不对
是的，这一点y总在视频中没细讲，这个刷视频刷到后面就豁然开朗了
能仔细说一下吗，我不是很懂
n为啥会变化呀，退出循环后n不还是96吗
同问，不理解n>1
for循环中的while循环对x做了除法 n/=i, 会变小；
例如第一个质因数i= 2 ，while循环后 n 是3；
继续枚举 i=3，3 > 3/3=1, 结束循环；
此时 n =3 。3 > sqrt(3)=1.7
ooo，这个意思感谢大佬
大佬厉害，所以是在讲解过程中出了问题，但是代码是没问题的
说说我个人对i是质数的看法，首先i是小于sqrt（n）的，i是从2开始递增，n只可能以2,3,5,7,11,13这样的数为除了1以外的最小因子，因为4，6，8，9，10，12等都是2，3等的倍数，所以i一定是质数
a=16的话，我咋感觉i=4可以输出呢？
“如果有两个大于sqrt(n)的因子，那么相乘会大于n，矛盾。证毕” 为什么要让这两个大雨sqrt(n)的因子相乘，他俩分别是两组不同的因子不行吗
“根据算术基本定理，不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。”
唯一
sry
设p,q为两个n的质因约数，设n=Ap,因为q|n,所以q|(Ap),因为(p,q)=1,所以q|A,不妨设A=Bq,则n=Bpq,所以pq|n
因为p,q>sqrt(n)所以pq大于n,所以不可能被n整除
“最后如果n还是>1，说明这就是大于sqrt(n)的唯一质因子，输出即可。”妙啊
数学大佬nb
谁能给我仔细的说一下为什么n > 1 ,代表的是大于根号的约数，还有n = 1的时候真的很不理解
首先质数的定义是指在大于1的自然数当中，除了1和它本身之外没有其他任何因数，然后每个数有且仅有一个大于根号n的因子（因为有两个的话相乘就矛盾了）所以当对于小于根号n的所有质因数都循环完的话，必定会剩下1和唯一那个大于根号n的质因子，因为它是质数，所以只需要特判它大于1就好了
剩下1或唯一那个质因子
已经明白了谢谢啦
int main(void)
为什么main这里要传一个void?
c语言必须要求void,C++可以省略，意思是传入给主函数的参数，用处在于当你用命令行运行程序时可以在后面填参数，这个地方就是接受参数的
c语言也可以省略void因为main函数不用传递参数所以也不需要写void（void就是无参数的意思），main函数可以把函数返回类型改成void这样return语句都不用写了
Orz
#Orz
好
这个优化真棒@
没错是我又来了，高数大佬tql
高数大佬牛逼！
抽风大佬也nb!!
高数大佬stO
高数大佬Orz