Instantly share code, notes, and snippets.

Embed
What would you like to do?
5761455 prime numbers - SECCON CTF Challenge post-game discussion

問題

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}"
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment