問題(和訳)

https://goo.gl/FVrD8 Problem 41 - PukiWiki

回答

awk 'BEGIN{for(i=1;i<=9;i++){a+=i;b=b""i;if(a%3)c=b"\n"c}print c}' | awk '$1>1{a="";for(i=1;i<=length($1);i++)a=substr($1,i,1)""a;for(i=a;i>=$1;i-=9)print i}' | awk '!/0/&&/[1379]$/{split("",a);for(i=1;i<=length($1);i++)if(a[substr($1,i,1)]++)next;for(i=length($1)+1;i<=9;i++)if($1~i)next;print}' | factor | awk 'NF==2{print;exit}'

7652413: 7652413
 
real   0m0.562s
user   0m0.810s
sys    0m0.000s

解説

素直に、9桁以下のパンデジタル数を大きい方から順に素数になるものを探す

 # n桁のパンデジタル数を生成 
 awk 'BEGIN{             
   for(i=1;i<=9;i++){
     a+=i;                   
     b=b""i;          
            
     # 3の倍数以外ならば出力の準備
     if(a%3)
 
       # 桁数の大きいものから順に並べる
       c=b"\n"c
   }
                                                            
   # 出力                                                                        
   print c       
 }' |
                                                  
 # パンデジタル数候補を大きい数字から生成する
 awk '$1>1{                  
 
   # 例えば $1=1234 のとき a=4321 を作る               
   a="";                    
   for(i=1;i<=length($1);i++)
     a=substr($1,i,1)""a;
                                           
   # パンデジタル数候補を生成  
   for(i=a;i>=$1;i-=9)
     print i                                                               
             
 }' |       
 
 # 解答条件に合う数値を抽出する
 awk '         
          
 # 0を含まず(含んだら1からnまでのパンデジタル数にならない)
 # かつ、奇数だけど末尾が5じゃないもののみ抽出(偶数や末尾が5の数は素数ではない)
 !/0/&&/[1379]$/{
                 
   # 各桁に重複が無いこと(を配列 a[数字] で検出)
   split("",a);                              
   for(i=1;i<=length($1);i++)
        
     # 重複してたら処理を中断し、次の入力行の処理に移る                 
     if(a[substr($1,i,1)]++)
       next;                 
                         
   # 桁数より大きい数値が無いことをチェック
   for(i=length($1)+1;i<=9;i++)
                      
     # 桁数より大きい数値が存在してたら処理を中断し、次の入力行の処理に移る
     if($1~i)                     
       next;
 
   # 条件に合致したら表示              
   print       
 }'     |
                                                            
 # 素因数分解(後続処理で素数かどうかを判断するため)                            
 factor |        
     
 # 最初の素数(最大の素数)を表示したら、即終了   
 awk 'NF==2{print;exit}'

トップ   編集 凍結 差分 履歴 添付 複製 名前変更 リロード   新規 一覧 検索 最終更新   ヘルプ   最終更新のRSS
Last-modified: 2019-03-24 (日) 07:44:02