2以上30以下の素数は次の10個です。
2 3 5 7 11 13 17 19 23 29
これらの素数の中で一番多く出現する数字は1で、5個出現します。2番目に多く出現する数字は2と3がそれぞれ3個ずつ出現します。
2以上10000以下の素数は1229個あり、それらの素数の中で一番多く出現する数字の個数は1の681個です。また2番目は3の677個、3番目は7の652個です。
2以上1億以下の素数は5761455個ありますが、この中で3番目に多く出現する数字の個数はいくつでしょうか?
5443074
Project Euler風味な問題。
1億以下の素数をプログラムで生成・列挙するのは時間がかかるので、"The Prime Pages"などにある素数テーブルを使うのが吉。
The Prime Pages
結果は次の通り
$ ./count_prime_numbers.rb 100000000 1 : count=5510645 3 : count=5472472 7 : count=5443074 9 : count=5432190 2 : count=4047829 4 : count=4022501 5 : count=4015732 6 : count=4007705 8 : count=3998411 0 : count=3386986 count=5761455
#!/usr/bin/ruby | |
base_url = "http://primes.utm.edu/lists/small/millions/" | |
base_name = "primes%d" | |
if ARGV.size < 1 | |
puts "usage: count_prime_numbers.rb [max_limit_num]" | |
exit 1 | |
end | |
max_limit_num = ARGV[0].to_i | |
num_a = Array.new(10){|i| [i,0]} | |
prime_count=0 | |
file_count=1 | |
catch(:finish) do | |
loop do | |
name = sprintf(base_name, file_count) | |
puts "target=#{name}" | |
# get primes table file | |
unless File.exist?(name + ".txt") | |
url = base_url + name + ".zip" | |
system("wget #{url}") | |
system("unzip " + name + ".zip") | |
end | |
file_count += 1 | |
# open primes table file | |
open(name + ".txt") do |f| | |
# skip headers | |
f.gets | |
f.gets | |
# read primes | |
while l = f.gets | |
l.chomp! | |
a = l.split(" ") | |
a.each {|s| | |
# check max_limit_num | |
throw :finish if max_limit_num < s.to_i | |
# count numbers | |
s.each_byte {|b| | |
n = b - 0x30 | |
num_a[n][1] = num_a[n][1] + 1 | |
} | |
prime_count += 1 | |
} | |
end | |
end | |
end | |
end | |
# print result | |
num_a = num_a.sort{|a,b| b[1] <=> a[1]} | |
num_a.each do |a| | |
puts "#{a[0]} : count=#{a[1]}" | |
end | |
puts "prime_count=#{prime_count}" |