Project Eulerをワンライナーで解いてみる。
間違っていたらコメントください。
問題
素数$3, 7, 109, 673$は非凡な性質を持っている. 任意の$2$つの素数を任意の順で繋げると, また素数になっている. 例えば, $7$と$109$を用いると, $7109$と$1097$の両方が素数である. これら$4$つの素数の和は$792$である. これは, このような性質をもつ$4$つの素数の集合の和の中で最小である.
任意の$2$つの素数を繋げたときに別の素数が生成される, $5$つの素数の集合の和の中で最小のものを求めよ.
解答
time seq 3 9999 |
factor |
awk 'NF==2{print $2}' |
tr '\n' ' ' |
awk '{for(i=1;i<=NF-1;i++){for(j=i+1;j<=NF;j++){print $i$j,$j$i,$i,$j}}}' |
factor |
awk 'NR%4==0{print $0} NR%4!=0{printf $0" "}' |
awk 'NF==8{print $6,$8}' |
awk '{if($1!=k){printf "\n"$0" "}else{printf $2" "};k=$1}' |
awk '{for(i=2;i<=NF-1;i++){for(j=i+1;j<=NF;j++){print $1,$i$j,$j$i,$i,$j}}}' |
factor |
awk 'NR%5==0{print $0} NR%5!=0{printf $0" "}' |
awk 'NF==10{print $2,$8,$10}' |
awk '{if($1$2!=k){printf "\n"$0" "}else{printf $3" "};k=$1$2}' |
awk '{for(i=3;i<=NF-1;i++){for(j=i+1;j<=NF;j++){print $1,$2,$i$j,$j$i,$i,$j}}}' |
factor |
awk 'NR%6==0{print $0} NR%6!=0{printf $0" "}' |
awk 'NF==12{print $2,$4,$10,$12}' |
awk '{if($1$2$3!=k){printf "\n"$0" "}else{printf $4" "};k=$1$2$3}' |
awk '{for(i=4;i<=NF-1;i++){for(j=i+1;j<=NF;j++){print $1,$2,$3,$i$j,$j$i,$i,$j}}}' |
factor |
awk 'NR%7==0{print $0} NR%7!=0{printf $0" "}' |
awk 'NF==14{print $2+$4+$6+$12+$14}'
26033
real 0m3.095s
user 0m5.717s
sys 0m0.140s
これも結局総当たりで解いた。フィルタコマンドの特性上、「○○を抽出する」や「○○以外を抽出する」といったロジックになってしまう。
よって、$2$つの素数をとって、くっつけて、factor
して合成数だったら除外する、という操作を繰り返した。
グラフ理論というものを使用すればもう少し楽に解けるらしいが、持っていない知識だったし、ワンライナーで活かせるか分からなかったので特に調べなかった。
もしかしたらもう少し短くできるのかもしれない。
答え合わせ
こちらのサイト様と一致していればOKとした。
http://kingyojima.net/pje/060.html