diff options
author | marcandre <marcandre@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2016-08-10 18:17:41 +0000 |
---|---|---|
committer | marcandre <marcandre@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2016-08-10 18:17:41 +0000 |
commit | c6742a0ae6313be120b38b554f5e3a16397e77c1 (patch) | |
tree | 71ee28418860cd687dad0d7632f71e6f4b8091c8 | |
parent | ea54cb9507b9c7e6657df1a52f7f51aa87c8019e (diff) | |
download | ruby-c6742a0ae6313be120b38b554f5e3a16397e77c1.tar.gz |
* lib/prime.rb: Optimize prime?
Adapted from patch by Jabari Zakiya [#12665]
* test/test_prime.rb: Improve test
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@55856 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
-rw-r--r-- | ChangeLog | 7 | ||||
-rw-r--r-- | lib/prime.rb | 11 | ||||
-rw-r--r-- | test/test_prime.rb | 17 |
3 files changed, 20 insertions, 15 deletions
@@ -1,3 +1,10 @@ +Thu Aug 11 03:16:59 2016 Marc-Andre Lafortune <ruby-core@marc-andre.ca> + + * 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@ruby-lang.org> * parse.y (command_rhs, arg_rhs): introduce new rules to reduce diff --git a/lib/prime.rb b/lib/prime.rb index c64c0c2cf1..a6700e3e8b 100644 --- a/lib/prime.rb +++ b/lib/prime.rb @@ -33,11 +33,12 @@ class Integer # 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 diff --git a/test/test_prime.rb b/test/test_prime.rb index b48ccae319..7f15894abf 100644 --- a/test/test_prime.rb +++ b/test/test_prime.rb @@ -140,17 +140,14 @@ class TestPrime < Test::Unit::TestCase end def test_prime? - # zero and unit - assert_not_predicate(0, :prime?) - assert_not_predicate(1, :prime?) - - # small primes - assert_predicate(2, :prime?) - assert_predicate(3, :prime?) + PRIMES.each do |p| + assert_predicate(p, :prime?) + end - # 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?) |