「プロジェクトオイラー問124」の編集履歴(バックアップ)一覧はこちら
「プロジェクトオイラー問124」(2014/03/09 (日) 01:55:59) の最新版変更点
追加された行は緑色になります。
削除された行は赤色になります。
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万個の要素のソート。
まあ普通です。
#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);
}
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);
}