Circular Primes v1

circular_primes_v1.rb

# O( N log N )

class Integer # in real apps should use refinements instead of monkey patching
  def prime?
    return false if self < 2
    ! 2.upto(self**0.5).any? { |n| self % n == 0 }
  end

  def rotations
    n, ss = to_s.length, to_s * 2
    0.upto(n-1).map { |offset| ss[offset, n].to_i }
  end
end

module CircularPrimes
  def self.upto(upper_limit)
    v = []
    1.upto(upper_limit) do |i| # O(n)
      v << i if i.rotations.all?(&:prime?) # O(log n) x O(n^0.5)
    end
    v
  end
end

if __FILE__ == $0
  max_n = ARGV[0]&.to_i || 1_000_000
  v = CircularPrimes.upto(max_n)
  puts "There are #{v.count} circular primes between 1 and #{max_n}"
end