#author("2017-07-14T18:24:55+09:00","default:nobuoki","nobuoki")
* 問題(和訳) [#l91fb7dd]
https://goo.gl/ZQ1j9c Problem 58 - PukiWiki

* 回答 [#x6a4f92e]
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

* 解説 [#db70f7ba]
 # 頂点になる値を生成し、素数判定し、割合を計算して 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
   }
 }'

* その他 [#w478fe18]
 # 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