筛法

我发现了，这种题还是挺容易卡时间的
要多用筛法防止超时
这题就是一个简单的质因数分解。
如果当前的数有至少两个质因数的话
那么就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);
}