make a list of prime numbers, using the binary search algorithm to search the prime table.

listprimes_binsearch.rb

#!/opt/local/bin/ruby1.9 -w
# -*- coding: utf-8 -*-
# listprimes_binsearch.rb: make a list of prime numbers.

def die(*x)
  STDERR.puts x
  exit 1
end

if ARGV.length < 2
  die <<USAGE
Usage: #{__FILE__} <start> <range>
print prime numbers (start <= primes < start + range)
USAGE
end

start = ARGV.shift.to_i
range = ARGV.shift.to_i

PRIMES_FILE = "primes.txt"
$primes = []

def ($primes).binsearch(n)
  len = self.size
  first = 0
  last = len - 1
  while len > 0
    mid = first + len / 2
    v = self[mid]
    if n == v
      return true
    elsif n < v
      last = mid - 1
    else
      first = mid + 1
    end
    len = last - first + 1
  end
  false
end

if File.exist?(PRIMES_FILE)
  File.foreach(PRIMES_FILE) do |line|
    $primes.push(line.to_i)
  end
end
$updated = false

$primes = [2] if $primes.size < 1
$max_prime = $primes[-1]

def prime_check(n)
  c = 1
  limit = Math::sqrt(n)
  $primes.each do |p|
    break if p > limit
    return [false, c] if (n % p == 0)
    c += 1
  end
  [true, c]
end

($max_prime...start).each do |n|
  next if $primes.include?(n)
  if prime_check(n)[0]
    $primes.push(n)
    $updated = true
  end
end
$max_prime = $primes[-1] if $updated

STDERR.puts "START (#{$max_prime}):\n"
start = 2 if start < 2
t0 = Time.now
(start...(start + range)).each do |n|
  if n <= $max_prime
    if $primes.binsearch(n)
      print "#{n} (0)\n"
    end
  else
    is_prime, counter = prime_check(n)
    if is_prime
      $primes.push(n)
      $updated = true
      print "#{n} (#{counter})\n"
    end
  end
end
elapsed = Time.now - t0
STDERR.puts "Elapsed: #{elapsed}\n"

if $updated
  File.open(PRIMES_FILE, "w") do |of|
    $primes.each do |p|
      of.puts(p)
    end
  end
end