5761455 prime numbers - SECCON CTF Challenge post-game discussion

challenge.md

問題

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番目に多く出現する数字の個数はいくつでしょうか？

comment.md

回答

5443074

解説

Project Euler風味な問題。

1億以下の素数をプログラムで生成・列挙するのは時間がかかるので、"The Prime Pages"などにある素数テーブルを使うのが吉。

The Prime Pages

• http://primes.utm.edu/

結果は次の通り

  $ ./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

count_prime_numbers.rb

#!/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}"