※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。

「プロジェクトオイラー問124」の編集履歴(バックアップ)一覧はこちら

プロジェクトオイラー問124」の最新版変更点

追加された行は青色になります。

削除された行は赤色になります。

 http://odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%20124
 http://projecteuler.net/problem=124
 
 
 *Problem 124 「順序付き根基」 †
 n の"根基"(radical)は, rad(n) に関する問題。
 詳細はリンク先参照のこと。
 
 
 解法
 エラトステネスの篩もどきでテーブル化して計算しソートし1万個めを求めるだけです。
 計算量BigO(366401)+10万個の要素のソート。
 まあ普通です。
-
-
+世の中J言語使いこなしてる人多いなと思います。
+J言語だとこの問題1行、究極のショートコードですね。
 
  #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);
  }