spec/math/prime_spec.cr

• View this file on GitHub
• Last update: 2022-04-14 22:36:43+09:00

Depends on

• src/math/prime.cr

Code

require "spec"
require "../../src/math/prime"

describe Prime do
  it "#unsafe_fetch(i)" do
    Prime.unsafe_fetch(0).should eq 2
    Prime.unsafe_fetch(1).should eq 3
    Prime.unsafe_fetch(2).should eq 5
    Prime.unsafe_fetch(999999).should eq 15485863
  end

  it "#size" do
    Prime.size.should eq 10**9
  end

  it "#each(x, &)" do
    primes = [] of Int32
    Prime.each(20) { |x| primes << x }
    primes.should eq [2, 3, 5, 7, 11, 13, 17, 19]
  end

  it "#each(x)" do
    Prime.each(20).to_a.should eq [2, 3, 5, 7, 11, 13, 17, 19]
    Prime.each(20).index(19).should eq 7
    Prime.each(20).index(23).should be_nil
    Prime.each(10**8).size.should eq 5761455
  end

  describe "includes Indexable" do
    it "#[](i)" do
      Prime[0].should eq 2
      Prime[1].should eq 3
      Prime[2].should eq 5
      expect_raises(IndexError) { Prime[-1] }
      expect_raises(IndexError) { Prime[10**9] }
    end

    it "#first" do
      Prime.first.should eq 2
    end
  end

  it "#[]?(start, count)" do
    Prime[0, 3]?.should eq [2, 3, 5]
    Prime[1, 3]?.should eq [3, 5, 7]
    Prime[2, 3]?.should eq [5, 7, 11]
    Prime[-2, 3]?.should be_nil
    expect_raises(ArgumentError) { Prime[0, -3]? }
  end

  it "#[](start, count)" do
    Prime[0, 3].should eq [2, 3, 5]
    Prime[1, 3].should eq [3, 5, 7]
    Prime[2, 3].should eq [5, 7, 11]
    expect_raises(IndexError) { Prime[-2, 3] }
    expect_raises(ArgumentError) { Prime[0, -3] }
  end

  it "#[]?(range)" do
    Prime[0...3]?.should eq [2, 3, 5]
    Prime[1...4]?.should eq [3, 5, 7]
    Prime[2...5]?.should eq [5, 7, 11]
    Prime[0..-3]?.should eq [] of Int32
    Prime[5..2]?.should eq [] of Int32
    Prime[...3]?.should eq [2, 3, 5]
    Prime[...-3]?.should eq [] of Int32
    expect_raises(IndexError) { Prime[-2..3]? }
    expect_raises(ArgumentError) { Prime[3..]? }
  end

  it "#[](range)" do
    Prime[0...3].should eq [2, 3, 5]
    Prime[1...4].should eq [3, 5, 7]
    Prime[2...5].should eq [5, 7, 11]
    Prime[0..-3].should eq [] of Int32
    Prime[5..2].should eq [] of Int32
    Prime[...3].should eq [2, 3, 5]
    Prime[...-3].should eq [] of Int32
    expect_raises(IndexError) { Prime[-2..3] }
    expect_raises(ArgumentError) { Prime[3..] }
  end

  it "#includes?(x)" do
    Prime.should_not contain -10**9
    Prime.should_not contain -1
    Prime.should_not contain 0
    Prime.should_not contain 57
    Prime.should_not contain 91
    Prime.should_not contain 9943081

    Prime.should contain 13
    Prime.should contain 10**6 + 3
    Prime.should contain 10**8 + 7
  end

  it "#index(x)" do
    Prime.index(2).should eq 0
    Prime.index(3).should eq 1
    Prime.index(5).should eq 2
    Prime.index(7).should eq 3
    Prime.index(10**8 + 7).should eq 5761455

    Prime.index(-10**9).should be_nil
    Prime.index(-1).should be_nil
    Prime.index(0).should be_nil
    Prime.index(1).should be_nil
    Prime.index(57).should be_nil
    Prime.index(91).should be_nil
    Prime.index(9943081).should be_nil
  end
end

require "spec"

# require "../../src/math/prime"
module Prime
  extend self
  include Indexable(Int32)

  @@primes = [
    2, 3, 5, 7, 11, 13, 17, 19, 23, 29,
    31, 37, 41, 43, 47, 53, 59, 61, 67, 71,
    73, 79, 83, 89, 97, 101, 103, 107, 109, 113,
    127, 131, 137, 139, 149, 151, 157, 163, 167, 173,
    179, 181, 191, 193, 197, 199, 211, 223, 227, 229,
    233, 239, 241, 251, 257, 263, 269, 271, 277, 281,
    283, 293, 307, 311, 313, 317, 331, 337, 347, 349,
    353, 359, 367, 373, 379, 383, 389, 397, 401, 409,
    419, 421, 431, 433, 439, 443, 449, 457, 461, 463,
    467, 479, 487, 491, 499, 503, 509, 521, 523, 541,
    547, 557, 563, 569, 571, 577, 587, 593, 599, 601,
    607, 613, 617, 619, 631, 641, 643, 647, 653, 659,
    661, 673, 677, 683, 691, 701, 709, 719, 727, 733,
    739, 743, 751, 757, 761, 769, 773, 787, 797, 809,
    811, 821, 823, 827, 829, 839, 853, 857, 859, 863,
    877, 881, 883, 887, 907, 911, 919, 929, 937, 941,
    947, 953, 967, 971, 977, 983, 991, 997,
  ]

  private def generate_primes : Nil
    size = @@primes.size
    primes = Array.new(size) { |i| @@primes.last + (i + 1) * 2 }
    last = primes.last

    @@primes.each do |prime|
      next if prime == 2
      break if prime * prime > last
      from = prime * ((@@primes.last // prime + 1) // 2 * 2 + 1)
      from.step(to: last, by: prime * 2) do |x|
        primes[~((last - x) // 2)] = 0
      end
    end

    @@primes.concat primes.reject(0)
  end

  private def generate_until(*, index : Int)
    while @@primes.size <= index
      generate_primes
    end
  end

  private def generate_until(*, value : Int)
    while @@primes.last < value
      generate_primes
    end
  end

  private def check_index_out_of_bounds(index)
    if 0 <= index < size
      index
    else
      yield
    end
  end

  # Returns the *index* th prime, without doing any bounds check.
  def unsafe_fetch(index : Int) : Int32
    generate_until(index: index)
    @@primes.unsafe_fetch(index)
  end

  # Returns the limit of size.
  def size : Int32
    10**9
  end

  def []?(start : Int, count : Int) : Array(Int32)?
    raise ArgumentError.new "Negative count: #{count}" if count < 0
    return [] of Int32 if start == size

    if 0 <= start <= size
      return [] of Int32 if count == 0

      count = Math.min(count, size - start)
      generate_until(index: start + count)

      Array(Int32).build(count) do |buffer|
        buffer.copy_from(@@primes.to_unsafe + start, count)
        count
      end
    end
  end

  def [](start : Int, count : Int) : Array(Int32)
    self[start, count]? || raise IndexError.new
  end

  private def self.range_to_index_and_count(range : Range, size : Int)
    end_index = range.end || raise ArgumentError.new
    end_index -= 1 if range.excludes_end?
    start_index = range.begin || 0
    raise IndexError.new unless start_index >= 0
    count = Math.max(end_index - start_index + 1, 0)
    {start_index, count}
  end

  def []?(range : Range) : Array(Int32)?
    self[*range_to_index_and_count(range, size)]?
  end

  def [](range : Range) : Array(Int32)
    self[*range_to_index_and_count(range, size)]
  end

  def includes?(x : Int) : Bool
    generate_until(value: x)
    @@primes.bsearch { |y| y >= x } == x
  end

  def index(x : Int) : Int32?
    generate_until(value: x)
    i = @@primes.bsearch_index { |y| y >= x }.not_nil!
    @@primes[i] == x ? i : nil
  end

  def each(x : Int, &) : Nil
    i = 0
    loop do
      generate_primes if @@primes.size == i
      prime = @@primes.unsafe_fetch(i)
      break if prime > x
      yield prime
      i += 1
    end
  end

  def each(x : Int)
    each.take_while { |prime| prime <= x }
  end
end

describe Prime do
  it "#unsafe_fetch(i)" do
    Prime.unsafe_fetch(0).should eq 2
    Prime.unsafe_fetch(1).should eq 3
    Prime.unsafe_fetch(2).should eq 5
    Prime.unsafe_fetch(999999).should eq 15485863
  end

  it "#size" do
    Prime.size.should eq 10**9
  end

  it "#each(x, &)" do
    primes = [] of Int32
    Prime.each(20) { |x| primes << x }
    primes.should eq [2, 3, 5, 7, 11, 13, 17, 19]
  end

  it "#each(x)" do
    Prime.each(20).to_a.should eq [2, 3, 5, 7, 11, 13, 17, 19]
    Prime.each(20).index(19).should eq 7
    Prime.each(20).index(23).should be_nil
    Prime.each(10**8).size.should eq 5761455
  end

  describe "includes Indexable" do
    it "#[](i)" do
      Prime[0].should eq 2
      Prime[1].should eq 3
      Prime[2].should eq 5
      expect_raises(IndexError) { Prime[-1] }
      expect_raises(IndexError) { Prime[10**9] }
    end

    it "#first" do
      Prime.first.should eq 2
    end
  end

  it "#[]?(start, count)" do
    Prime[0, 3]?.should eq [2, 3, 5]
    Prime[1, 3]?.should eq [3, 5, 7]
    Prime[2, 3]?.should eq [5, 7, 11]
    Prime[-2, 3]?.should be_nil
    expect_raises(ArgumentError) { Prime[0, -3]? }
  end

  it "#[](start, count)" do
    Prime[0, 3].should eq [2, 3, 5]
    Prime[1, 3].should eq [3, 5, 7]
    Prime[2, 3].should eq [5, 7, 11]
    expect_raises(IndexError) { Prime[-2, 3] }
    expect_raises(ArgumentError) { Prime[0, -3] }
  end

  it "#[]?(range)" do
    Prime[0...3]?.should eq [2, 3, 5]
    Prime[1...4]?.should eq [3, 5, 7]
    Prime[2...5]?.should eq [5, 7, 11]
    Prime[0..-3]?.should eq [] of Int32
    Prime[5..2]?.should eq [] of Int32
    Prime[...3]?.should eq [2, 3, 5]
    Prime[...-3]?.should eq [] of Int32
    expect_raises(IndexError) { Prime[-2..3]? }
    expect_raises(ArgumentError) { Prime[3..]? }
  end

  it "#[](range)" do
    Prime[0...3].should eq [2, 3, 5]
    Prime[1...4].should eq [3, 5, 7]
    Prime[2...5].should eq [5, 7, 11]
    Prime[0..-3].should eq [] of Int32
    Prime[5..2].should eq [] of Int32
    Prime[...3].should eq [2, 3, 5]
    Prime[...-3].should eq [] of Int32
    expect_raises(IndexError) { Prime[-2..3] }
    expect_raises(ArgumentError) { Prime[3..] }
  end

  it "#includes?(x)" do
    Prime.should_not contain -10**9
    Prime.should_not contain -1
    Prime.should_not contain 0
    Prime.should_not contain 57
    Prime.should_not contain 91
    Prime.should_not contain 9943081

    Prime.should contain 13
    Prime.should contain 10**6 + 3
    Prime.should contain 10**8 + 7
  end

  it "#index(x)" do
    Prime.index(2).should eq 0
    Prime.index(3).should eq 1
    Prime.index(5).should eq 2
    Prime.index(7).should eq 3
    Prime.index(10**8 + 7).should eq 5761455

    Prime.index(-10**9).should be_nil
    Prime.index(-1).should be_nil
    Prime.index(0).should be_nil
    Prime.index(1).should be_nil
    Prime.index(57).should be_nil
    Prime.index(91).should be_nil
    Prime.index(9943081).should be_nil
  end
end

Back to top page