Problem 7

素数を小さい方から6つ並べると 2, 3, 5, 7, 11, 13 であり、6番目の素数は 13 である。
10001 番目の素数を求めよ。

Problem 7 - PukiWiki

$p_list =[]
limit =10001

def prime_number?(num)
  return false if num < 2
  k = true
  (3..num).each{|i|
    $p_list.each{|j| k = false and break if i%j == 0 && num%i==0}
    break if !k
  }
  return  k
end

target = 1
while $p_list.size <= limit-1
  $p_list.push(target) if prime_number?(target)
  target +=1
end

p $p_list[limit-1]

とやってみたものの答え出ず。
仕方ない,考え付く高速化を試してみましょう。

include Math
def prime_number?(num,pl)
  return false if num < 2
  return true if num==2 || num==3|| num==5|| num==7|| num==11|| num==13|| num==17|| num==19|| num==23|| num==29
  return false if num %2==0 ||num%3==0 ||num%5==0 ||num % 7==0||num % 11==0||num % 13==0||num % 17==0||num % 19==0||num % 23==0||num % 29==0

  r = sqrt(num) 
  pl.each{|j|
    break if  j > r
    return false if num %j == 0
  }
  return  true
end

p_list =[]
limit =10001

target = 1
while p_list.size <= limit-1
  p_list.push(target) if prime_number?(target,p_list)
  target +=1
end

p p_list[limit-1]

答え：104743

条件が若干汚いですが、初めの方で枝狩りすることで実行時間が半分ぐらいになりました。