// November 17th, 2009 // No Comments » // programming, ruby
To find all primes up to a limit or to check if a number is prime or not, the sieve of eratosthenes is famously used. There are many known optimisations to the basic algorithm, also should check for simple things like if number is even or not. Maybe not just if the number is divisible by 2 but also 3, 5, 7, 11, etc. I remember there is a graph that points this out. Namely, that when there are multiple algorithms each with different time complexities, the algorithm that has average best performance may not have best performance especially for smaller datasets. I cant find that graph right now, but I am looking.
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
27
28
29
30
31
32
33
| #!/usr/bin/ruby -w
# Tue Nov 17 00:06:30 EST 2009
# patternexon AT gmail
# Under GPL v3.0
class Integer
/*
Sift the Twos and sift the Threes,
The Sieve of Eratosthenes.
When the multiples sublime,
The numbers that remain are Prime.
*/
def primes_upto(limit)
primes = Array.new
putative = Array(2..limit)
putative.each_index do |i|
primes.push(putative[i])
(i+1).upto(putative.size-1) do |j|
putative[j] = nil if putative[j] % putative[i] == 0
end
putative.compact!
end
return primes
end
def prime?
if self == self.primes_upto(self).last
return true
else
return false
end
end
end
1.upto(100){ |i| puts "#{i} is #{i.prime?}" } |
