Created
July 22, 2008 07:05
-
-
Save robolson/686 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Calculate all the primes between 0 and the value specified | |
def primes(up_to) | |
prev = [] | |
(2..up_to).select do |x| | |
max_p = Math.sqrt(x).truncate | |
if !prev.find { |y| y <= max_p ? x % y == 0 : break } | |
prev << x | |
end | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
require 'mathn' | |
class Fixnum | |
# Return true if self is a prime number | |
def prime? | |
max = Math.sqrt(self).ceil | |
max -= 1 if max % 2 == 0 | |
pgen = Prime.new | |
pgen.each do |factor| | |
return false if self % factor == 0 | |
return true if factor > max | |
end | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# Slower than prime2 | |
class Fixnum | |
# Return true if self is a prime number | |
def prime? | |
('1' * self) !~ /^1?$|^(11+?)\1+$/ | |
end | |
end |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
# http://www.rubyinside.com/using-rubyinline-to-speed-up-code-by-10x-159.html | |
require "rubygems" | |
require "inline" | |
class Primes | |
inline do |builder| | |
builder.c ' | |
int prime(int num) { | |
int x; | |
for (x = 2; x < (num - 1) ; x++) { | |
if (num == 2) { | |
return 1; | |
} | |
if (num % x == 0) { | |
return x; | |
} | |
} | |
return 1; | |
}' | |
end | |
end | |
p = Primes.new | |
for num in 2..10_000 do | |
is_prime = p.prime(num) | |
if is_prime == 1 | |
puts "#{num} is a prime number" | |
else | |
puts "#{num} equals #{is_prime} * #{num/is_prime}" | |
end | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment