今天的题选自Project Euler 35
数字197有个特性，轮转其每一位数字，得到197，971，719，结果都是质数。
请打出100万以内，具有以上特性的数字。
PS：注意，是轮转，不是全排列。

这题略有点难度，提示一下
100以上满足条件的数字只可能由[1，3，7，9]这4个数字组成。

PS: 上午睡足了，下午不到一个小时连刷3题，爽~

[ 本帖最后由 bbschat 于 2008-4-10 15:01 编辑 ]

为什么我总看不到我自己的名字

你发帖了吗？光解决问题是不会显示名字的，名字表示该题论坛最后一个发帖的人。

看一下先

[ 本帖最后由 love8909 于 2008-4-11 21:14 编辑 ]

这题其实不是很难，继续保留。大家加油。

我来抛砖吧，写的有点复杂，应该还有优化空间，我机器上 0.8秒

[Copy to clipboard] [ - ]

CODE:

[hide]
  t0 = Time.now

  def is_prime?(n)
    sqar = (n ** 0.5).to_i   
    3.step(sqar, 2) do |i|
      return true if i > n
      return false if n % i == 0
    end

  end
  
  def is_circular_prime(n)
    result = [n]
    n_size = n.to_s.size
    if n_size == 1
      $num_result << n if is_prime?(n)
      return result
    else
      1.upto(n_size - 1) {result << result.last.divmod(10)[1] * (10 ** (n_size - 1)) + result.last.divmod(10)[0]}
      result.uniq!
    end
    
    result.each {|r| return result if not is_prime?(r)}
    $num_result += result
    return result
  end

  $num_all = $num_type = [1,3,7,9]
  $num_result = [2,5]
  
  1.upto(5) {|i|
    temp = []
    $num_all.each {|x| $num_type.each {|y| temp << x * 10 + y}}
    $num_all |= temp
    }
  
  until $num_all.size == 0
    $num_all -= is_circular_prime($num_all[0])
  end
  
  p ($num_result - [1]).size
  
  p Time.now - t0
[/hide]