欧拉筛

求最小质因数

const int LIM = 1e6+10;
int miniFactor[LIM],prime[LIM / 3];
int primepos;

void euler() {
    int tmp;
    for (int i = 2; i < LIM; i++) {
        if (!miniFactor[i]) prime[primepos++] = i, miniFactor[i] = i;
        for (int j = 0; (tmp = i * prime[j]) < LIM; j++) {
            miniFactor[tmp] = prime[j];
            if (!(i % prime[j])) break;
        }
    }
}

void solve(){
    int n;
    scanf("%d", &n);
    printf("%d\n", miniFactor[n]);
};

int main(){
    euler();
    int t;
    cin>>t;
    while(t--)
        solve();
    return 0;
}

留下评论