纯埃氏筛法求素因子
AC代码(含注释)
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;//定义long long为ll
ll prime[40005], ans[40005], x, xx, cnt, flag;
int main()
{//求解40000以内的素数(埃氏筛)
for (ll i = 1; i <= 40000; i++)//40000的平方大于1e9
prime[i] = 1; x = 2;//初始化数组中所有数为1
while (x <= 40000)
{
for (ll j = 2; j*x <= 40000; j++)
{
if (prime[x] == 1)//2为素数
{
prime[j*x] = 0;//素数的倍数即非素数初始化为0
}
}
x++;
}
//判断素数
ll T, m;
cin >> T;
while (T--)//使得输出全部结束后不会换行
{
ll ans[40005] = { 0 };//或者memset(ans,0,sizeof(ll));
cnt = 0;
cin >> xx;
x = xx;//防止xx的原始输入值变化
for (ll i = 2; i <= floor(sqrt(xx)) + 1; i++)//floor(sqrt(xx))+1一定小于40000
{
if (x == 1) break;//如果x=1,说明循环结束,立刻终止循环,防止其继续存入数组
if (x <= 40000 && prime[x] == 1)//如果x是40000内的素数
{
ans[++cnt] = x;//或者cnt=cnt+1;ans[cnt]=x;
//将x存入数组ans中,此时ans[1]=x
break;//退出for循环
}
//如果x不是40000内的素数
if (prime[i] == 1 && x%i == 0)//如果i是素数因子
{
while (x%i == 0) x /= i;//让x一直除i,直到i不是x的素数因子为止
//注意:x如果是40000内的非素数,其经历多次while循环的结果必为1
//如果x=1,就会继续循环到上面存入数组,产生干扰(上面埃氏筛没有将1筛选成非素数)
ans[++cnt] = i;//或者cnt=cnt+1;ans[cnt]=i;
//将x的素数因子i按从小到大的顺序存入数组ans中
}
}//for循环结束
//如果循环后x>40000,则剩下的这个x一定是素数
//反证法:如果剩下的x不是素数,则其必定被小于40000的素数因子循环掉
if (x>40000) ans[++cnt] = x;//或者cnt=cnt+1;ans[cnt]=x;
if (cnt == 1 && ans[1] == xx) cout << "isprime" << endl;
else cout << "noprime" << endl;
for (ll i = 1; i <= cnt; i++)
{
if (i == cnt) cout << ans[i];
else cout << ans[i] << " ";
}
if (T != 0) cout << endl;
}
return 0;
}