#!/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 !
James Koppel
October 1, 2007, October 01, 2007 15:04, permalink
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.
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
michiel
October 1, 2007, October 01, 2007 19:40, permalink
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.
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
michiel
October 1, 2007, October 01, 2007 19:55, permalink
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.
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
Paul Kemper
October 4, 2007, October 04, 2007 06:10, permalink
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.
<?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]);
}
?>
killian
October 5, 2007, October 05, 2007 10:26, permalink
@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...
Dave Grijalva
October 7, 2007, October 07, 2007 05:36, permalink
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.
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}"}
michiel
October 7, 2007, October 07, 2007 16:28, permalink
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.
primes = Array.new(nil, ceiling + 1)
Alexander Pas
May 14, 2010, May 14, 2010 13:25, permalink
Unrolling the loop a bit can increase the speed by almost 20% (enable skipping multiples of 5)
#!/usr/bin/ruby
require 'benchmark'
include Math
GC.disable
class Integer
def is_prime?
if (self =< 9)
return true if self == 2
return true if self == 3
return true if self == 5
return true if self == 7
return false
end
return false if self % 2 == 0
return false if self % 3 == 0
return false if self % 5 == 0
return false if self % 7 == 0
ss = sqrt(self).floor
return false if ss**2 == self
i=11
while i <= ss
return false if self % i == 0 # i % 10 == 1
i += 2 # skip even numbers
if i <= ss # simulating the while loop.
return false if self % i == 0 # i % 10 == 3
i += 4 # skip even numbers and also skip i % 10 == 5
if i <= ss # simulating the while loop.
return false if self % i == 0 # i % 10 == 7
i += 2 # skip even numbers
if i <= ss # simulating the while loop.
return false if self % i == 0 # i % 10 == 9
i += 2 # skip even numbers
end
end
end
end
return true
end
end
# test it
primes = []
puts Benchmark.realtime{(1..100000).each{|x|primes << x if x.is_prime?}}
puts primes.size
Raving Genius
October 12, 2010, October 12, 2010 12:53, permalink
Fixed a typo on line 9 of the previous example.
#!/usr/bin/ruby
require 'benchmark'
include Math
GC.disable
class Integer
def is_prime?
if self <= 9
return true if self == 2
return true if self == 3
return true if self == 5
return true if self == 7
return false
end
return false if self % 2 == 0
return false if self % 3 == 0
return false if self % 5 == 0
return false if self % 7 == 0
ss = sqrt(self).floor
return false if ss**2 == self
i=11
while i <= ss
return false if self % i == 0 # i % 10 == 1
i += 2 # skip even numbers
if i <= ss # simulating the while loop.
return false if self % i == 0 # i % 10 == 3
i += 4 # skip even numbers and also skip i % 10 == 5
if i <= ss # simulating the while loop.
return false if self % i == 0 # i % 10 == 7
i += 2 # skip even numbers
if i <= ss # simulating the while loop.
return false if self % i == 0 # i % 10 == 9
i += 2 # skip even numbers
end
end
end
end
return true
end
end
# test it
primes = []
puts Benchmark.realtime{(1..100000).each{|x|primes << x if x.is_prime?}}
puts primes.size
Adam
October 14, 2010, October 14, 2010 04:55, permalink
A different approach using the built-in Prime class. It is not going to win any speed records calculating the primes, but it does cache the results.
require 'mathn'
require 'set'
require 'singleton'
class PrimeSet < Prime
include Singleton
def initialize
@set = Set.new
super
end
def succ
super.tap { |integer| @set << integer }
end
def include?(integer)
succ until @seed > integer
@set.include?(integer)
end
end
class Integer
def prime?
PrimeSet.instance.include?(self)
end
end
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.