筛法
我发现了,这种题还是挺容易卡时间的
要多用筛法防止超时
这题就是一个简单的质因数分解。
如果当前的数有至少两个质因数的话
那么就ok否则就no
#include<iostream> #include<algorithm> using namespace std; typedef pair<int,int> pii; const int max_n = 5e5+100; const int max_m = 1e7+100; pii ans[max_n]; int n; int isprime[max_m]; int prime[max_m]; int main(){ fill(prime,prime+max_m,-1); for (int i=2;i<=10000000;++i){ if (isprime[i]!=0)continue; for (int j=i+i;j<=10000000;j+=i){ isprime[j]++; prime[j]=i; } } scanf("%d",&n); for (int i=1;i<=n;++i){ int num;scanf("%d",&num); if (isprime[num]<2)ans[i]=pii(-1,-1); else { int f = prime[num]; while (num%f==0)num/=f; ans[i]=pii(f,num); } } for (int i=1;i<=n;++i)printf("%d ",ans[i].first);printf("\n"); for (int i=1;i<=n;++i)printf("%d ",ans[i].second); }