marcandre	2016-08-11 03:17:41 +0900 (Thu, 11 Aug 2016)

  New Revision: 55856

  https://svn.ruby-lang.org/cgi-bin/viewvc.cgi?view=revision&revision=55856

  Log:
    * lib/prime.rb: Optimize prime?
      Adapted from patch by Jabari Zakiya [#12665]
    
    * test/test_prime.rb: Improve test

  Modified files:
    trunk/ChangeLog
    trunk/lib/prime.rb
    trunk/test/test_prime.rb
Index: lib/prime.rb
===================================================================
--- lib/prime.rb	(revision 55855)
+++ lib/prime.rb	(revision 55856)
@@ -33,11 +33,12 @@ class Integer https://github.com/ruby/ruby/blob/trunk/lib/prime.rb#L33
   # Returns true if +self+ is a prime number, else returns false.
   def prime?
     return self >= 2 if self <= 3
-    return false if self % 2 == 0 or self % 3 == 0
-    (5..(self**0.5).floor).step(6).each do |i|
-      if self % i == 0 || self % (i + 2) == 0
-        return false
-      end
+    return true if self == 5
+    return false unless 30.gcd(self) == 1
+    (7..Math.sqrt(self).to_i).step(30) do |p|
+      return false if
+        self%(p)    == 0 || self%(p+4)  == 0 || self%(p+6)  == 0 || self%(p+10) == 0 ||
+        self%(p+12) == 0 || self%(p+16) == 0 || self%(p+22) == 0 || self%(p+24) == 0
     end
     true
   end
Index: ChangeLog
===================================================================
--- ChangeLog	(revision 55855)
+++ ChangeLog	(revision 55856)
@@ -1,3 +1,10 @@ https://github.com/ruby/ruby/blob/trunk/ChangeLog#L1
+Thu Aug 11 03:16:59 2016  Marc-Andre Lafortune  <ruby-core@m...>
+
+	* lib/prime.rb: Optimize prime?
+	  Adapted from patch by Jabari Zakiya [#12665]
+
+	* test/test_prime.rb: Improve test
+
 Wed Aug 10 22:37:01 2016  Nobuyoshi Nakada  <nobu@r...>
 
 	* parse.y (command_rhs, arg_rhs): introduce new rules to reduce
Index: test/test_prime.rb
===================================================================
--- test/test_prime.rb	(revision 55855)
+++ test/test_prime.rb	(revision 55856)
@@ -140,17 +140,14 @@ class TestPrime < Test::Unit::TestCase https://github.com/ruby/ruby/blob/trunk/test/test_prime.rb#L140
     end
 
     def test_prime?
-      # zero and unit
-      assert_not_predicate(0, :prime?)
-      assert_not_predicate(1, :prime?)
+      PRIMES.each do |p|
+        assert_predicate(p, :prime?)
+      end
 
-      # small primes
-      assert_predicate(2, :prime?)
-      assert_predicate(3, :prime?)
-
-      # squared prime
-      assert_not_predicate(4, :prime?)
-      assert_not_predicate(9, :prime?)
+      composites = (0..PRIMES.last).to_a - PRIMES
+      composites.each do |c|
+        assert_not_predicate(c, :prime?)
+      end
 
       # mersenne numbers
       assert_predicate((2**31-1), :prime?)

--
ML: ruby-changes@q...
Info: http://www.atdot.net/~ko1/quickml/