![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
sh/Problem 37
Top/sh/Problem 37https://kemasoft.net/?sh/Problem+37
https://goo.gl/0QmZY Problem 37 「切り詰め可能素数」
seq 11 999999 | grep -v '[0468]' | grep -v '.[25]' | grep '^[2357]' | grep '[37]$' | factor | awk 'NF==2{print $2}' | sed 's/./& /g' | awk '$1==$2{next}$(NF-1)==$NF{next}{print}' | awk '{a=0;for(i=1;i<=NF-1;i++){a+=$i;if(a%3==0 && i>1){next}}print}' | awk '{a=0;for(i=NF;i>1;i--){a+=$i;if(a%3==0 && i<NF){next}}print}' | tr -d ' ' | awk 'BEGIN{ORS=""}{print $1" ";for(i=2;i<length($1);i++){print substr($1,i)" "substr($1,1,i)" "};print "\n"}' |awk '{for(i=2;i<=NF;i++){cmd="factor "$i"|awk \047{print NF}\047"; cmd|getline f;close(cmd);if(f!=2){next}}print $1}' |awk '{a+=$1;print NR,$0}END{print "\nanswer: "a}'
1 23 2 37 3 53 4 73 5 313 6 317 7 373 8 797 9 3137 10 3797 11 739397 answer: 748317 real 0m0.309s user 0m0.060s sys 0m0.020s
# 答えは2桁以上で、（たぶん）100万以下の整数だろう・・・
seq 11 999999 |
# 2以外の偶数を含む数値は、右から切り詰めた時に末尾に来ると素数じゃないので除外
grep -v '[0468]' |
# 先頭以外で 2,5 を含む数値は右から切り詰めると素数じゃないので除外
grep -v '.[25]' |
# 1桁に切り詰めても素数になるには、先頭は [2357] 末尾は [37] になるはず
grep '^[2357]' | grep '[37]$' |
# その中から素数を抽出
factor | awk 'NF==2{print $2}' |
# 以降の処理のために、一旦1桁ごとに分解する
sed 's/./& /g' |
# 頭2桁 or 末尾2桁がゾロ目は、切り詰めたときに11の倍数なので省く
awk '$1==$2{next}$(NF-1)==$NF{next}{print}' |
# 左右から切り詰めたときに3の倍数になるものを除く
awk '{a=0;for(i=1;i<=NF-1;i++){a+=$i;if(a%3==0 && i>1){next}}print}' |
awk '{a=0;for(i=NF;i>1;i--){a+=$i;if(a%3==0 && i<NF){next}}print}' |
# 以降の処理のために、一旦各桁を結合する
tr -d ' ' |
# 切り詰め数を生成（頭と後ろの両方から）
awk 'BEGIN{ORS=""}{print $1" ";for(i=2;i<length($1);i++){print substr($1,i)" "substr($1,1,i)" "};print "\n"}' |
# 切り詰め数が素数でないものを除く
awk '{for(i=2;i<=NF;i++){cmd="factor "$i"|awk \047{print NF}\047"; cmd|getline f;close(cmd);if(f!=2){next}}print $1}' |
# 答えを算出
awk '{a+=$1;print NR,$0}END{print "\nanswer: "a}'
