Ideone.com

download

copy

require 'set'
 
@primes = Set.new([2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67])
 
def is_prime? num
  if num < 2
    return false
  end
  if num <= 67
    return @primes.include?(num)
  else
    @primes.each do |prime|
      return false if num % prime == 0
    end
  end
  miller_rabin_test(num)  
end
 
 
def list_of_tests n
  if n < 1373653
    [2,3]
  elsif n < 9080191
    [31,73]
  elsif n < 4759123141
    [2,7,61]
  elsif n < 2152302898747
    [2,3,5,7,11]
  elsif n < 3474749660383
    [2,3,5,7,11,13]
  elsif n < 341550071728321
    [2,3,5,7,11,13,17]
  end
end
 
def pow_mod(base, power, mod)
  result = 1
  while power > 0
    result = (result * base) % mod if power & 1 == 1
    base = (base * base) % mod
    power >>= 1;
  end
  result
end
 
def miller_rabin_test num
  n = num-1
  s,d = compute_s_and_d(num)
  list_of_tests(num).each do |a|
    break if a >= num
    x = pow_mod(a,d,num)
    #puts "x = #{x}"
    next if x == 1 or x == n
    skip = false
    (0..s-1).each do |r|
       x = pow_mod(x,2,num)
       #puts "r = #{r}, x = #{x}, n = #{n}"
       return false if x == 1
       if x == n
         skip = true
         break
       end
    end
    next if skip
    return false
  end
  return true
end
 
def compute_s_and_d n
  s = 0
  d = n - 1
  while d % 2 == 0
    d /= 2
    s += 1
  end
  return [s,d]
end
 
def find_primes min, max
  if min <= 2
    min = 3
    puts "2"
  end
  start = min.odd? ? min : min+1
  (start..max).step(2) do |num|
    if is_prime?(num)
      STDOUT.write("#{num}\n")
    end
  end
end
 
 
 
ranges = []
 
STDIN.each_with_index do |line,index|
  next if index == 0
  ranges << line.split.map{|num| num.to_i}
end
 
ranges.each do |range|
  find_primes *range
  STDOUT.write("\n")
end

cmVxdWlyZSAnc2V0JwoKQHByaW1lcyA9IFNldC5uZXcoWzIsMyw1LDcsMTEsMTMsMTcsMTksMjMsMjksMzEsMzcsNDEsNDMsNDcsNTMsNTksNjEsNjddKQoKZGVmIGlzX3ByaW1lPyBudW0KICBpZiBudW0gPCAyCiAgICByZXR1cm4gZmFsc2UKICBlbmQKICBpZiBudW0gPD0gNjcKICAgIHJldHVybiBAcHJpbWVzLmluY2x1ZGU/KG51bSkKICBlbHNlCiAgICBAcHJpbWVzLmVhY2ggZG8gfHByaW1lfAogICAgICByZXR1cm4gZmFsc2UgaWYgbnVtICUgcHJpbWUgPT0gMAogICAgZW5kCiAgZW5kCiAgbWlsbGVyX3JhYmluX3Rlc3QobnVtKSAgCmVuZAoKCmRlZiBsaXN0X29mX3Rlc3RzIG4KICBpZiBuIDwgMTM3MzY1MwogICAgWzIsM10KICBlbHNpZiBuIDwgOTA4MDE5MQogICAgWzMxLDczXQogIGVsc2lmIG4gPCA0NzU5MTIzMTQxCiAgICBbMiw3LDYxXQogIGVsc2lmIG4gPCAyMTUyMzAyODk4NzQ3CiAgICBbMiwzLDUsNywxMV0KICBlbHNpZiBuIDwgMzQ3NDc0OTY2MDM4MwogICAgWzIsMyw1LDcsMTEsMTNdCiAgZWxzaWYgbiA8IDM0MTU1MDA3MTcyODMyMQogICAgWzIsMyw1LDcsMTEsMTMsMTddCiAgZW5kCmVuZAoKZGVmIHBvd19tb2QoYmFzZSwgcG93ZXIsIG1vZCkKICByZXN1bHQgPSAxCiAgd2hpbGUgcG93ZXIgPiAwCiAgICByZXN1bHQgPSAocmVzdWx0ICogYmFzZSkgJSBtb2QgaWYgcG93ZXIgJiAxID09IDEKICAgIGJhc2UgPSAoYmFzZSAqIGJhc2UpICUgbW9kCiAgICBwb3dlciA+Pj0gMTsKICBlbmQKICByZXN1bHQKZW5kCgpkZWYgbWlsbGVyX3JhYmluX3Rlc3QgbnVtCiAgbiA9IG51bS0xCiAgcyxkID0gY29tcHV0ZV9zX2FuZF9kKG51bSkKICBsaXN0X29mX3Rlc3RzKG51bSkuZWFjaCBkbyB8YXwKICAgIGJyZWFrIGlmIGEgPj0gbnVtCiAgICB4ID0gcG93X21vZChhLGQsbnVtKQogICAgI3B1dHMgInggPSAje3h9IgogICAgbmV4dCBpZiB4ID09IDEgb3IgeCA9PSBuCiAgICBza2lwID0gZmFsc2UKICAgICgwLi5zLTEpLmVhY2ggZG8gfHJ8CiAgICAgICB4ID0gcG93X21vZCh4LDIsbnVtKQogICAgICAgI3B1dHMgInIgPSAje3J9LCB4ID0gI3t4fSwgbiA9ICN7bn0iCiAgICAgICByZXR1cm4gZmFsc2UgaWYgeCA9PSAxCiAgICAgICBpZiB4ID09IG4KICAgICAgICAgc2tpcCA9IHRydWUKICAgICAgICAgYnJlYWsKICAgICAgIGVuZAogICAgZW5kCiAgICBuZXh0IGlmIHNraXAKICAgIHJldHVybiBmYWxzZQogIGVuZAogIHJldHVybiB0cnVlCmVuZAoKZGVmIGNvbXB1dGVfc19hbmRfZCBuCiAgcyA9IDAKICBkID0gbiAtIDEKICB3aGlsZSBkICUgMiA9PSAwCiAgICBkIC89IDIKICAgIHMgKz0gMQogIGVuZAogIHJldHVybiBbcyxkXQplbmQKCmRlZiBmaW5kX3ByaW1lcyBtaW4sIG1heAogIGlmIG1pbiA8PSAyCiAgICBtaW4gPSAzCiAgICBwdXRzICIyIgogIGVuZAogIHN0YXJ0ID0gbWluLm9kZD8gPyBtaW4gOiBtaW4rMQogIChzdGFydC4ubWF4KS5zdGVwKDIpIGRvIHxudW18CiAgICBpZiBpc19wcmltZT8obnVtKQogICAgICBTVERPVVQud3JpdGUoIiN7bnVtfVxuIikKICAgIGVuZAogIGVuZAplbmQKCgoKcmFuZ2VzID0gW10KClNURElOLmVhY2hfd2l0aF9pbmRleCBkbyB8bGluZSxpbmRleHwKICBuZXh0IGlmIGluZGV4ID09IDAKICByYW5nZXMgPDwgbGluZS5zcGxpdC5tYXB7fG51bXwgbnVtLnRvX2l9CmVuZAoKcmFuZ2VzLmVhY2ggZG8gfHJhbmdlfAogIGZpbmRfcHJpbWVzICpyYW5nZQogIFNURE9VVC53cml0ZSgiXG4iKQplbmQK

Runtime error #stdin #stdout 1.64s 5540KB

stdin

copy

10
999000000 999100000
999100000 999200000
999200000 999300000
999300000 999400000
999400000 999500000
999500000 999600000
999600000 999700000
999700000 999800000
999800000 999900000
999900000 1000000000

stdout

copy

https://ideone.com/Fmsoh

language:

Ruby (ruby 2.5.5)

created:

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!

Discover > Sphere Engine API

Discover > IDE Widget

Choose your language