POJ 3048 Max Factor（素数，水题）

素数，水题
题目意思：
给出n个整数，要求数组这些整数中，拥有素因子最大的哪个整数。如果有多个，输出最早出现的那个。
本题要点：
1、n <= 20000, 先打素数表。然后对于每一个 数a[i], 求出其最大的素因子 max_fac[i].
最后扫描数组 max_fac， 找出最大的那个即可。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 20010;
int n;
int a[MaxN], prime[MaxN], pNum;
int max_fac[MaxN];
bool vis[MaxN];void solve()
{
    vis[0] = vis[1] = 1;for(int i = 2; i < MaxN; ++i){
    if(!vis[i]){
    prime[pNum++] = i;for(int j = i + i; j < MaxN; j += i)vis[j] = 1;}}for(int i = 1; i <= n; ++i){
    int k = a[i];for(int j = 0; prime[j] * prime[j] <= a[i]; ++j){
    if(k % prime[j] == 0){
    max_fac[i] = prime[j];while(k % prime[j] == 0)k /= prime[j];}}if(k > 1)max_fac[i] = k;}int ans = -1, index = 0;for(int i = 1; i <= n; ++i){
    if(ans < max_fac[i]){
    ans = max_fac[i], index = i;}}printf("%d\n", a[index]);
}int main()
{
    scanf("%d", &n);for(int i = 1; i <= n; ++i)scanf("%d", &a[i]);solve();	return 0;
}/* 4 36 38 40 42 *//* 38 */