PKU 3048-Max Factor

問題概要

1から20000までの数字がN個与えられる．最も大きい素数を約数に含みかつ出来るだけ早く出てきた数を答えよ

解法

篩の応用で最大の素数を求めることが出来る．
篩より計算量はかなり悪い．

実装(C)

#include <stdio.h>
#define MAX_N 20001
int max_prime[MAX_N];
int main() {
	int i=0,j;
	for(i=1;i<MAX_N;i++)max_prime[i]=1;
	for(int i=2;i<=MAX_N;i++){
		if(max_prime[i]==1){
			for(j=i*2;j<MAX_N;j+=i){
				max_prime[j]=i;
			}
		}
	}
	for(i=1;i<MAX_N;i++){
		if(max_prime[i]==1)max_prime[i]=i;
	}
	int n;
	scanf("%d",&n);
	int mp=1,t;
	for(int i=0;i<n;i++){
		scanf("%d",&t);
		if(max_prime[t]>max_prime[mp]){
			mp=t;
		}
	}
	printf("%d\n",mp);
	return 0;
}