质因数分解板子

对2-sqrt(n)每个数d进行扫描，如果d|n，则d是n的因子，则从N中除去所有的因子d，同时累计除去的d的个数。

因为一个合数的因子一定会在扫描到这个合数之前就从N中被去除，所有筛出来的是质数。

举个例子： 20，当从2开始的时候，就会把2的倍数都剔除了。20–>10–>5,直到不能被2除

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1e5;
typedef long long LL;
LL p[maxn],c[maxn];
void divide(LL n)
{
	LL m=0;
	for(LL i=2;i<=sqrt(n);i++)
	{
		if(n%i==0)//i是质数 
		{
			p[++m]=i;c[m]=0;
			while(n%i==0) n/=i,c[m]++;//除掉所有的i	
		}	
	} 
	if(n>1)//n还是质数
		p[++m]=n,c[m]=1;
	for(LL i=1;i<=m;i++)
		cout<<p[i]<<"^"<<c[i]<<endl;	 
}
int main(void)
{
  cin.tie(0);std::ios::sync_with_stdio(false);
 
return 0; 
}

本文地址：https://blog.csdn.net/zstuyyyyccccbbbb/article/details/107486183