试除法分解质因数
首先我们要了解一下正常的数学做法:
所以我们只需要进行这些步骤的模拟即可,也就是从2开始遍历循环不停的进行除法:
步骤详解
从2开始往后做除法,第一个能被除开的数一定是原数n的一个质数
for(int i=2;i<=n/i;i++)
if(n%i==0)
如果这个数是,那么继续对这个数轮番进行除法,且记录指数
int s=0;
while(n%i==0)
{
n/=i;
s++;
}
而如果除到最后n>1那么说明最后的这个n也是n的一个质数
为什么可以这样?
因为
n中最多只包含一个大于根号n的质因子
if(n>1)printf("%d %d\n",n,1);
算法1
进行数学模拟试除法来计算质数
C++ 代码
#include<bits/stdc++.h>
using namespace std;
void divide(int n)
{
for(int i=2;i<=n/i;i++)
if(n%i==0)//i一定是质数
{
int s=0;
while(n%i==0)
{
n/=i;
s++;
}
printf("%d %d\n",i,s);
}
if(n>1)printf("%d %d\n",n,1);
puts("");
}
int main()
{
int n;
scanf("%d",&n);
while(n--)
{
int x;
scanf("%d",&x);
divide(x);
}
return 0;
}
%%%
太强了