問題(和訳)

https://goo.gl/kiFFv3 Problem 47 - PukiWiki

回答

seq 1000000 | factor | awk 'NF>4{split("",a);for(i=2;i<=NF;i++)a[$i]++;sub(":","",$1);printf $1" ";for(v in a)printf v" ";print ""}' | awk 'NF==5{a[NR%4]=$1;if(a[(NR+3)%4]==($1-1)&&a[(NR+2)%4]==($1-2)&&a[(NR+1)%4]==($1-3)){print a[(NR+1)%4],a[(NR+2)%4],a[(NR+3)%4],a[NR%4];exit}}'

134043 134044 134045 134046

real    0m0.296s
user    0m0.310s
sys     0m0.010s

解説

愚直に4つの素因数を持つ数値を求め、最初に連続している箇所を探す

 # 数値は適当・・・
 seq 1000000 |   
           
 # 素因数分解
 factor      |
                                                             
 # 素因数の数(種類)を求める
 # factor の出力結果の重複を無くす
 awk 'NF>4{                                                 
              
   # 因数を格納する配列を初期化
   split("",a);                
                               
   # 各因数を配列(の添字)に格納      
   for(i=2;i<=NF;i++)                                                
     a[$i]++;
                 
   # 元の数を表示するために、余計な ':' を削除         
   sub(":","",$1);
                               
   # 出力形式: 元の数 因数1 因数2 因数3 ...
   printf $1" ";
   for(v in a)
     printf v" ";
   print ""                         
 }' |
 
 # 素因数を4つ持つものについて、4つ連番になっているものを探す
 awk 'NF==5{     
                                    
   # 現在行と過去3行分のデータを配列に格納(リングバッファ)
   a[NR%4]=$1;
                                                             
   # 1つ前との差が1であり、かつ
   # 2つ前との差が2であり、かつ
   # 3つ前との差が3であれば、それが答え                     
   if(a[(NR+3)%4]==($1-1)&&a[(NR+2)%4]==($1-2)&&a[(NR+1)%4]==($1-3)){
 
     # 答えを表示              
     print a[(NR+1)%4],a[(NR+2)%4],a[(NR+3)%4],a[NR%4];
                                       
     # 以降の入力を無視して終了                                      
     exit
   }             
 }'

備考

「最初に現れるそれぞれ4つの異なる素因数を持つ連続する4つの数」とのことだが、仮に4つの同じ素因数を持つ数字が「連続する4つの数」に現れることは無いので、「4つの異なる素因数」のチェックはしていない。

4つの異なる素因数を持つ最小の数は、
  2*3*5*7 = 210
これと同じ素因数を持つ、次に小さい数は、
  2^2*3*5*7 = 420
となり、連続する4つの数に入らない。

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