2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

Project Euler Q60 【素数ペア集合】

Posted at

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で

2
2
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
2
2

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?