Avatar

This is as fast as I could get this method, as tested by looking for all the primes in 1..100000. Disabling garbage collection, skipping even numbers (by incrementing the counter by 2), and only testing up through sqrt(self) all helped while remaining accurate, but I know it could be faster. Please note I'm not looking for the fastest prime-finding algorithm, which wouldn't necessarily be suitable to efficiently testing whether a given number is prime. Thanks.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#!/usr/bin/ruby
require 'benchmark'
include Math

GC.disable

class Integer
  def is_prime?
    i=3
    return false if self % 2 == 0 and self != 2
    ss = sqrt(self).floor
    return false if ss**2 == self
    while i <= ss
      return false if self % i == 0
      i += 2
    end
    return true
  end
end

# test it
primes = []
puts Benchmark.realtime{(1..100000).each{|x|primes << x if x.is_prime?}}
puts primes.size

Refactorings

No refactoring yet !

2922715cbee99df9b47619992cf5c9ae

James Koppel

October 1, 2007, October 01, 2007 15:04, permalink

No rating. Login to rate!

Do you need to test whether a number is prime, or is extraordinarily likely prime satisfactory? If the latter is the case, use Fermat's Little Theorem, which states that, if p is a prime, a^p mod p = a for any integer a. I've included a basic implementation.

1
2
3
4
5
6
7
8
class Integer
  def is_prime?
    2 ** self % self == 2 and
    3 ** self % self == 3 and
    5 ** self % self == 5 and
    7 ** self % self == 7
  end
end
7c45f63f61e478233f0c2ad3006b178c

michiel

October 1, 2007, October 01, 2007 19:40, permalink

No rating. Login to rate!

This is equally long, and 20% faster. Not as elegant as Fermat's Little Theorem, but I don't know how many tests you need to get acceptable accuracy.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
require 'benchmark'
include Math

GC.disable

PR = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
class Integer
  def is_prime?
    return PR.include?(self) if self < 53
    PR.each {|y| return false if self % y == 0 }
    i = 53
    ss = sqrt(self).floor
    while i <= ss
      return false if self % i == 0
      i += 2
    end
    true
  end
end

# test it
primes = []
puts Benchmark.realtime{(1..100000).each{|x|primes << x if x.is_prime?}}
puts primes.size
7c45f63f61e478233f0c2ad3006b178c

michiel

October 1, 2007, October 01, 2007 19:55, permalink

No rating. Login to rate!

This is a concise implementation of Fermat's Little Theorem. But don't run it because it is really slow. You need an algorithm to calculate a^p % p without actually calculating a^p, since a == 47 and p == 100000 in this example. You can probably find it in Knuth, second volume.

1
2
3
4
5
6
7
8
class Integer
  PR = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
  def is_prime?
    PR.all? {|x| x ** self % self == x}
  end
end

# don't run
F23409c4ed7fffe188d39a23e3a1527f

Paul Kemper

October 4, 2007, October 04, 2007 06:10, permalink

No rating. Login to rate!

If you have a maximum upper bound to the numbers you want to test (100000 in your example), I would just calculate a fixed array which holds all primes up to 100000, serialize the array to disk and load it again when you need to test. Use that array to verify the numbers against.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
<?php
// SOrry, stated in PHP
// Create the full array somehow:

$primes = array(
  1 => true,
  2 => true,
  3 => true,
  5 => true,
...
  999991 => true
);

// Write to disk
serialize( $primeArray, 'primearray.ser' );
?>

<?php
// Pull array from permanent storage
$primeArray = unserialize('primearray.ser');
function isPrime( $n )
{
  global $primeArray;
  return isset($primeArray[$n]);
}
?>
46065dc281559097b0dd10a34cdbb806

killian

October 5, 2007, October 05, 2007 10:26, permalink

No rating. Login to rate!

@michiel "You need an algorithm to calculate a^p % p without actually calculating a^p"

http://en.wikipedia.org/wiki/Modular_exponentiation

(a * b) mod c = ((a mod c) * (b mod c)) mod c

Just transform a^p into a * a * a * ... (p times).
(a * a * a * ...) = ((a mod c) * (a mod c) * (a mod c) * ...) mod c

Python have a function for this, don't know about ruby...

584559348afbc5cc06c46c3b5746313a

Dave Grijalva

October 7, 2007, October 07, 2007 05:36, permalink

1 rating. Login to rate!

Here's a quick way to get all the primes up to a certain number. You'll find it's very fast as it uses only addition.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def primes_up_to ceiling
  primes = [false, true]
  for i in (2..ceiling)
    if primes[i] == nil
      primes[i] = true

      j = i*2
      while j <= ceiling
        primes[j] = false
        j += i
      end 
    end
  end
  
  primes
end

primes_up_to(10000).each_with_index{|v, i| puts "#{i}: #{v}"}
7c45f63f61e478233f0c2ad3006b178c

michiel

October 7, 2007, October 07, 2007 16:28, permalink

No rating. Login to rate!

Looks good, David! One nitpick is that since you know the size of the array, it's faster to initialize it with that size. I'd leave is_prime? undefined for 0 and 1.

1
primes = Array.new(nil, ceiling + 1)

Your refactoring





Format Copy from initial code

or Cancel