プロジェクトオイラー問１２４ - c21coterie @ ウィキ

http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20124
http://projecteuler.net/problem=124

Problem 124 「順序付き根基」 †

n の"根基"(radical)は, rad(n) に関する問題。
詳細はリンク先参照のこと。

解法
エラトステネスの篩もどきでテーブル化して計算しソートし１万個めを求めるだけです。
計算量ＢｉｇＯ（366401）+１０万個の要素のソート。
まあ普通です。
世の中Ｊ言語使いこなしてる人多いなと思います。
Ｊ言語だとこの問題１行、究極のショートコードですね。

#include<stdio.h>
#include<algorithm>

struct E{
	int n,rad;
	bool operator<(const E& e)const{
		if(rad!=e.rad)return rad<e.rad;
		return n<e.n;
	}
};
const int LIMIT=100000;
int main(){
	E rads[LIMIT+1];
	int bigO=0;
	for(int i=0;i<=LIMIT;i++){
 		rads[i].n=i;
		rads[i].rad=1;
		bigO++;
	}
	for(int i=2;i<=LIMIT;i++){
		if(rads[i].rad>1)continue;
		for(int j=i;j<=LIMIT;j+=i){
 			bigO++;
			rads[j].rad*=i;
		}
	}
	std::sort(rads,rads+LIMIT+1);
	printf("ans=%d BigO=%d\n",rads[10000].n,bigO);
}