diff options
author | yugui <yugui@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2008-09-03 13:57:21 +0000 |
---|---|---|
committer | yugui <yugui@b2dd03c8-39d4-4d8f-98ff-823fe69b080e> | 2008-09-03 13:57:21 +0000 |
commit | fce093432eadc191b3647f116a9c2f6748efda3e (patch) | |
tree | 08292b34a1435b87391cf0c11e042fca14443d00 /test/test_prime.rb | |
parent | 9cab7d15ca791d0b14db03217485a7c756097a71 (diff) | |
download | ruby-fce093432eadc191b3647f116a9c2f6748efda3e.tar.gz |
* lib/mathn.rb (Integer): moved into prime.rb.
(Prime): ditto.
* lib/prime.rb (Integer): moved from mathn.rb.
(Integer.each_prime): added.
(Integer#prime?): added.
(Prime): moved from mathn.rb.
Its implmentation was rewritten. see [ruby-dev:35863].
And patched by Keiju ISHITSUKA <keiju@ishitsuka.com>,
see [ruby-dev:36128].
(Prime.new): obsolete.
(Prime.instance): added.
(Prime.each): added.
(Prime.int_from_prime_division): added.
(Prime.prime_division): added.
(Prime.prime?): added.
Patch by TOYOFUKU Chikanobu
<nobu_toyofuku at nifty.com> in [ruby-dev:36067].
(Prime.cache): removed.
(Prime.primes): removed.
(Prime.primes_so_far): removed.
(Prime#int_from_prime_division): added.
(Prime#prime_division): added.
(Prime#prime?): added.
(Prime#primes): removed.
(Prime#primes_so_far): removed.
(Prime::PseudoPrmeGenerator): added.
(Prime::EratosthenesGenerator): added.
(Prime::TrialDivisionGenerator): added.
(Prime::Generator23): added.
(Prime::TrialDivision): added.
Extracted from the previous implementation of Prime
by Keiju ISHITSUKA.
(Prime::EratosthenesSieve): added.
* lib/.document (prime.rb): added
* lib/README (prime.rb): added
* test/test_prime.rb: added.
git-svn-id: svn+ssh://ci.ruby-lang.org/ruby/trunk@19095 b2dd03c8-39d4-4d8f-98ff-823fe69b080e
Diffstat (limited to 'test/test_prime.rb')
-rw-r--r-- | test/test_prime.rb | 126 |
1 files changed, 126 insertions, 0 deletions
diff --git a/test/test_prime.rb b/test/test_prime.rb new file mode 100644 index 0000000000..aca5109689 --- /dev/null +++ b/test/test_prime.rb @@ -0,0 +1,126 @@ +require 'test/unit' +require 'prime' +require 'stringio' + +class TestPrime < Test::Unit::TestCase + # The first 100 prime numbers + 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, + ] + def test_each + primes = [] + Prime.each do |p| + break if p > 541 + primes << p + end + assert_equal PRIMES, primes + end + + def test_each_by_prime_number_theorem + 3.upto(15) do |i| + max = 2**i + primes = [] + Prime.each do |p| + break if p >= max + primes << p + end + + # Prime number theorem + assert primes.length >= max/Math.log(max) + delta = 0.05 + li = (2..max).step(delta).inject(0){|sum,x| sum + delta/Math.log(x)} + assert primes.length <= li + end + end + + def test_each_without_block + enum = Prime.each + assert enum.respond_to?(:each) + assert enum.kind_of?(Enumerable) + assert enum.respond_to?(:with_index) + assert enum.respond_to?(:next) + assert enum.respond_to?(:succ) + assert enum.respond_to?(:rewind) + end + + def test_new + buf = StringIO.new('', 'w') + orig, $stderr = $stderr, buf + + enum = Prime.new + assert !buf.string.empty? + $stderr = orig + + assert enum.respond_to?(:each) + assert enum.kind_of?(Enumerable) + assert enum.respond_to?(:succ) + + assert Prime === enum + ensure + $stderr = orig + end + + def test_enumerator_succ + enum = Prime.each + assert_equal PRIMES[0, 50], 50.times.map{ enum.succ } + assert_equal PRIMES[50, 50], 50.times.map{ enum.succ } + enum.rewind + assert_equal PRIMES[0, 100], 100.times.map{ enum.succ } + end + + def test_enumerator_with_index + enum = Prime.each + last = -1 + enum.with_index do |p,i| + break if i >= 100 + assert_equal last+1, i + assert_equal PRIMES[i], p + last = i + end + end + + class TestInteger < Test::Unit::TestCase + def test_prime_division + pd = PRIMES.inject(&:*).prime_division + assert_equal PRIMES.map{|p| [p, 1]}, pd + end + + def test_from_prime_division + assert_equal PRIMES.inject(&:*), Integer.from_prime_division(PRIMES.map{|p| [p,1]}) + end + + def test_prime? + # small primes + assert 2.prime? + assert 3.prime? + + # squared prime + assert !4.prime? + assert !9.prime? + + # mersenne numbers + assert (2**31-1).prime? + assert !(2**32-1).prime? + + # fermat numbers + assert (2**(2**4)+1).prime? + assert !(2**(2**5)+1).prime? # Euler! + + # large composite + assert !((2**13-1) * (2**17-1)).prime? + + # factorial + assert !(2...100).inject(&:*).prime? + end + end +end |