問題(和訳)

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}'

トップ   編集 凍結 差分 バックアップ 添付 複製 名前変更 リロード   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2017-08-15 (火) 22:03:04