プロジェクトオイラー問124 - sinapusu2002 @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20124
Problem 124 「順序付き根基」 †
rad(n)に関係する問題。

解法
全部計算してソートするだけです。

#include <iostream>
#include<algorithm>
#include<vector>
#include<stdio.h>
using namespace std;

const int LIMIT=100000;
int memo[LIMIT+1];
bool isPrime[LIMIT+1];

struct E{
 	int n,m;
	bool operator<(const E& e)const{
		if(m!=e.m)return m<e.m;
		return n<e.n;
	}
};
int main() {
	for(int i=1;i<=LIMIT;i++){
		memo[i]=1;
		isPrime[i]=true;
	}
	for(int i=2;i<=LIMIT;i++){
		if(isPrime[i]==false)continue;
 		for(int j=i;j<=LIMIT;j+=i){
			if(i!=j)isPrime[j]=false;
			memo[j]*=i;
		}
	}
	std::vector<E> es;
	E e1;
 	for(int i=1;i<=LIMIT;i++){
		e1.n=i;
		e1.m=memo[i];
		es.push_back(e1);
	}
	std::sort(es.begin(),es.end());
 	printf("%d %d\n",es[9999].n,es[9999].m);
	return 0;
}