問題(和訳)

https://goo.gl/ZQ1j9c Problem 58 - PukiWiki

回答

awk 'BEGIN{print 1;for(i=1;;i++){a=(2*i+1)^2;printf "%d\n%d\n%d\n%d\n",a,a-2*i,a-4*i,a-6*i}}' | factor | awk 'NF==2{a++}NR>1&&NR%4=
=1{p=100*a/NR;if(p<10){print "l="int(NR/4)*2+1,p"%";exit}}'

l=26241 9.99981%

real   0m0.098s
user   0m0.120s
sys    0m0.000s

解説

頂点になる値を生成し、素数判定し、割合を計算して 10% 未満になったら終了

頂点になる値の特徴

  • n週目の最後の四つ角の値は、必ず正方形の角になるから (n+1)^2 になる (これを X とする)
  • 残りの3つの角は n週目との差/4 だけ離れているから、[ (n+1)^2-(n-1)^2 ] / 4 = 2n 毎に並ぶ
    • つまり頂点は X, X-2n, X-4n, X-6n となる
  • 辺の長さは、両方の頂点がカウントされるから 2n+1 となる
     # 頂点になる値を生成
     awk 'BEGIN{
     
       # 1だけは特別扱い
       print 1;
     
       # n週目の頂点を作る
       for(i=1;;i++){
     
         # n週目の最後の頂点
         a=(2*i+1)^2;
     
         # 各頂点を出力
         printf "%d\n%d\n%d\n%d\n",a,a-2*i,a-4*i,a-6*i
       }
     }'     |
     
     # 因数分解
     factor |
     
     # 判定
     awk '
     
     # 素数だったらカウンタを増加
     NF==2{
       a++
     }
     # n週目毎(4で割って1余る行数目毎、ただし1行目は除く)に素数の割合をチェック
     NR>1&&NR%4==1{
     
       # 素数の割合(百分率)を算出
       p=100*a/NR;
     
       # 10%未満になったら、答えを表示して終了
       if(p<10){
         print "l="int(NR/4)*2+1,p"%";
         exit
       }
     }'
    

その他

# n週目毎に途中経過を出力させる
awk 'BEGIN{print 1;for(i=1;;i++){a=(2*i+1)^2;printf "%d\n%d\n%d\n%d\n",a,a-2*i,a-4*i,a-6*i}}' | factor | awk 'NF==2{a++}NR>1&&NR%4==1{p=100*a/NR;print "NR="NR,"a="a,"l="int(NR/4)*2+1,p"%";if(p<10)exit}'

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