Project

General

Profile

Feature #16468 ยป prime_patch.diff

steveb3210 (Stephen Blackstone), 02/20/2020 07:19 PM

View differences:

lib/prime.rb
32 32

  
33 33
  # Returns true if +self+ is a prime number, else returns false.
34 34
  def prime?
35
    return self >= 2 if self <= 3
36
    return true if self == 5
37
    return false unless 30.gcd(self) == 1
38
    (7..Integer.sqrt(self)).step(30) do |p|
39
      return false if
40
        self%(p)    == 0 || self%(p+4)  == 0 || self%(p+6)  == 0 || self%(p+10) == 0 ||
41
        self%(p+12) == 0 || self%(p+16) == 0 || self%(p+22) == 0 || self%(p+24) == 0
42
    end
43
    true
35
    # https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
36
    # https://arxiv.org/pdf/1509.00864.pdf
37
    #
38
    # if n < 3,317,044,064,679,887,385,961,981,
39
    # it is enough to test a = 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, and 41.
40
    # and the result will be deterministic.
41
    #
42

  
43
    if self > 3317044064679887385961981
44
      raise ArgumentError, ".prime? is only valid for values less than 3,317,044,064,679,887,385,961,981"
45
    end
46
    
47
    return false if self < 2
48
    return true  if self < 4
49
    return false if self.even?
50

  
51
    r = 0
52
    d = self - 1
53

  
54
    while d.even?
55
      d /= 2
56
      r += 1
57
    end
58

  
59
    [2,3,5,7,11,13,17,19,23,29,31,37,41].each do |a|
60
      x = a.pow(d, self)
61
      next if x == 1 || x == (self-1) || a == self
62

  
63
      (r-1).times do
64
        x = x.pow(2, self)
65
        if x == (self-1)
66
          break
67
        end
68
      end
69

  
70
      if (x == self-1)
71
        next
72
      else
73
        return false
74
      end
75
    end
76
    return true
44 77
  end
45 78

  
46 79
  # Iterates the given block over all prime numbers.
test/test_prime.rb
219 219

  
220 220
      assert_equal(-PRIMES.inject(&:*), Integer.from_prime_division([[-1, 1]] + PRIMES.map{|p| [p,1]}))
221 221
    end
222

  
222
    
223
    def test_prime_bounds_check
224
       assert_raise(ArgumentError) { 33170440646798873859619812.prime? }
225
    end
226
        
223 227
    def test_prime?
224 228
      PRIMES.each do |p|
225 229
        assert_predicate(p, :prime?)
......
241 245
      # large composite
242 246
      assert_not_predicate(((2**13-1) * (2**17-1)), :prime?)
243 247

  
244
      # factorial
245
      assert_not_predicate((2...100).inject(&:*), :prime?)
246

  
247 248
      # negative
248 249
      assert_not_predicate(-1, :prime?)
249 250
      assert_not_predicate(-2, :prime?)