「e の小数点以下の数字で、最初に現れる10桁の素数を見つけなさい」


　数年前にGoogleが入社試験(正確には社員募集情報への入り口のヒント)で出した問題だそうです。

　アルゴリズム＆プログラミングの勉強として、Rubyで書いてみました。
　詳しく知りたい方は、ネットで検索してみてください。
　「マクローリン展開」「エラストテネスのふるい」あたりがキーワードでしょうか。


googleTest.rb 
#! /usr/bin/ruby

require 'napier.rb'
require 'primes.rb'

$primes = pcalc(100000)

def prime?(i)
    $primes.each do |prime|
        return false if((i % prime) == 0)
    end
    return true
end

e = ecalc(1000)
(2..(e.size-10)).each do |i|
    a = e[i, 10]
    if((a[0].chr != '0') && (prime?(a.to_i))) then
        p [i-2, a]
        exit
    end
end



napier.rb 
#! /usr/bin/ruby

def ecalc(n=15)
    one = ("1"+"0"*n).to_i
    work = one

    start = n * Math::log(10.0)

    (start+1).to_i.downto 1 do |n|
        work /= n
        work += one
    end

    return work.to_s.insert(1,'.')
end

=begin
    e = ecalc(ARGV[0].to_i)
    puts e
=end



primes.rb 
#! /usr/bin/ruby

def pcalc(n=1000)
    primes = (0...n).to_a
    primes[0] = 0
    primes[1] = 0
    primes.each_index do |i|
        next if(primes[i] == 0)
        (2..(n/i)).each do |j|
            primes[i*j] = 0
        end
    end
    primes.delete(0)

    return primes
end

=begin
    primes = pcalc(1000)
    p primes.size
    p primes
=end