Bash
ProjectEuler
数学

Project Euler Q60 【素数ペア集合】

More than 1 year has passed since last update.

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


参考にさせて頂いたサイト様

Project Euler 60 _ 素数ペア集合 - PEをMathematicaで