fork download
copy 
  1. # return base ^ exp % mod
  2. def modpow(base, exp, mod)
  3.   result = 1
  4.   while exp > 0
  5.     result = (result * base) % mod if exp & 1 == 1
  6.     exp >>= 1
  7.     base = base ** 2 % mod
  8.   end
  9.   result
  10. end
  11.  
  12. # http://j...content-available-to-author-only...a.org/wiki/%E3%83%9F%E3%83%A9%E3%83%BC-%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
  13. def prime?(n)
  14.   return true if n == 2
  15.   return false if n == 1 || n & 1 == 0
  16.   d = n - 1
  17.   d >>= 1 while d & 1 == 0
  18.   20.times do                               
  19.     a = rand(n - 2) + 1
  20.     t = d
  21.     y = modpow(a, t, n)                  
  22.     while t != n - 1 && y != 1 && y != n - 1
  23.       y = y ** 2 % n
  24.       t <<= 1
  25.     end
  26.     return false if y != n - 1 && t & 1 == 0
  27.   end
  28.   true
  29. end
  30.  
  31. def palinds_downto(bound)
  32.   return bound.downto(1) if bound < 10
  33.   sbound = bound.to_s
  34.   size = sbound.size
  35.   half_front = sbound[0, size / 2]
  36.   half_back  = sbound[size / 2 + (size & 1), size]
  37.   odd_size = size % 2 == 1
  38.   pivot = odd_size ? sbound[size / 2].to_i : 9
  39.   Enumerator.new do |y|
  40.     init = half_front.to_i
  41.     lower_bound = 10 ** (half_front.size - 1)
  42.     if half_back.to_i > half_front.reverse.to_i
  43.       if odd_size
  44.         y << "#{half_front}#{pivot}#{half_front.to_s.reverse}".to_i
  45.         pivot -= 1
  46.       end
  47.     else
  48.       init -= 1
  49.     end
  50.     while init > 0
  51.       if odd_size
  52.         init.downto(lower_bound) do |n|
  53.           s = n.to_s
  54.           pivot.downto(0).each {|p| y << "#{s}#{p}#{s.reverse}".to_i }
  55.           pivot = 9
  56.         end
  57.         odd_size = false
  58.         init = lower_bound * 10 - 1
  59.       else
  60.         init.downto(lower_bound) do |n|
  61.           s = n.to_s
  62.           y << (s + s.reverse).to_i
  63.         end
  64.         odd_size = true
  65.         init = lower_bound - 1
  66.         lower_bound /= 10
  67.       end
  68.     end
  69.     9.downto(1) {|i| y << i }
  70.   end
  71. end
  72.  
  73. puts palinds_downto(2 ** 80).find {|i| prime?(i) }
  74. puts palinds_downto(2 ** 30).find {|i| prime?(i) }
Success #stdin #stdout 0.07s 7476KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1208925819613169185298021
999727999
https://ideone.com/aOUvbD
language:
Ruby (ruby 2.5.5)
created:
11 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!