私自身が表題の問題を解いた時のプログラムについて解説します。
問題の詳細は「素数で度数分布表を作ろう！」（CodeIQ）を参照してください。
成績の分布などを表すのに使われる度数分布表。
ひと目で全体の散らばり具合がわかって便利です。
階級（点） 度数（人） 0〜20 3 21〜40 6 41〜60 9 61〜80 13 81〜100 14 計 45
【問題】
今回は素数の度数分布表を作ってみます。
入力として2つの正の整数が与えられます。
一つ目は分布させる素数の最大値(最大20000)、二つ目は区切りの大きさです。
例えば、30と5が与えられたとき、30までの素数を5で区切って出力します。
30までの素数は2, 3, 5, 7, 11, 13, 17, 19, 23, 29ですので、出力内容は以下のようになります。
01-05:***
06-10:*
11-15:**
16-20:**
21-25:*
26-30:*
同様に、40と7が与えられると、以下のように出力されます。
01-07:****
08-14:**
15-21:**
22-28:*
29-35:**
36-42:*
【入出力サンプル】
Input
30 5
Output
01-05:***
06-10:*
11-15:**
16-20:**
21-25:*
26-30:*
Rubyで解答しています。
#!/usr/bin/ruby
require 'prime'
def getFreq(m,n)
ret = [0]
cnt = 1
Prime.each(m){|v|
if v > cnt*n then
ret << 0
cnt += 1
end
ret[cnt-1] += 1
}
return ret
end
def printFreq(m,n, counts)
len = m.to_s.size.to_s
fmt = "%0" + len + "d-%0" + len + "d:%s\n"
counts.each_with_index{|cnt, i|
st = 1 + i * n
ed = (i+1) * n
printf(fmt, st, ed, "*" * cnt)
}
end
def solve(m,n)
counts = getFreq(m,n)
printFreq(m,n, counts)
end
# main
while line = gets
line.strip!
if line.empty? then next end
m,n = line.split.map{|a| a.to_i}
solve(m,n)
end
簡単な問題です。特にRubyの場合素数リストを求める手段が標準で組み込まれているので簡単です。
この問題は仕様の説明に漏れがあります。階級の表示を最大の値の桁数に合わせて0埋めしなければならないのですが明示されていません。例を見ると0埋めが必要かな、とわかるのですが明示されるべきと思います。
考え方と言うほどのものはありませんが、次のようにしています。
まず、階級ごとに素数の数を数えます。
そしてそれを表示用にフォーマットして表示します。
階級ごとに素数を数えて度数のリストを返します。
素数リストはPrime.each()で列挙できるので階級ごとにカウントします。
ちょっと考えなければいけない部分があるとしたら階級の区切りをどうするかですが、階級の初期値を1にしておいて（6行目）、n*階級を超える素数が現れたら階級を1増やす（8〜11行目）ことでできます。と、言いたいところですがこれにはバグがあります。テストケースでは相当するテストがないのでパスしていますが、頻度0の階級があるとおかしくなります。
なので単純に最初から領域を確保してしまって、素数の値/nの商の要素のカウントを増やすようにするのが正しいです。
結果を表示します。引数は入力値（m,n）とgetFreq()で作成した度数のデータ(counts)です。
基本的にcountsの数だけ"*"を表示すれば良いのですが、書式を整えなければなりません。こういう時はprintf()が最強で0埋めもフォーマット文字列で指定できます。このフォーマット文字列を別途桁数に合わせて作成（18〜19行目）しておけばあとは簡単に出力できます。
getFreq()を読んで度数リストを取得し、printFreq()で表示するだけです。
こういうプログラムは仕事でもログの調査などのために何回か作ったことがあります。
2つの関数に分けるのはループ回数的にちょっと無駄なのですが、最大20000までしかないのでプログラムをわかりやすくするため分けました。