PatternExon

Sieve of Eratosthenes

// 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?}" }

Project Euler – Problem 14

// August 13th, 2009 // No Comments » // programming, project euler, ruby

Why is this an image?

Project Euler – Problem 10

// August 3rd, 2009 // No Comments » // programming, project euler, ruby

Why is this an image?

Project Euler Problem 9

// July 23rd, 2009 // No Comments » // programming, project euler, ruby

Why is this an image?

Project Euler – Problem 8

// July 20th, 2009 // No Comments » // programming, project euler, ruby

Why is this an image?

Project Euler – Problem 7

// July 12th, 2009 // No Comments » // programming, project euler, ruby

Why is this an image?

Project Euler – Problem 6

// July 6th, 2009 // No Comments » // project euler, ruby

Project Euler – Problem 5

// June 30th, 2009 // No Comments » // project euler, ruby

Project Euler 5

Ok. I have to admit this took more time in getting there.

I did not want to brute force the answer and I did not remember how GCD is calculated.

I do like that looping – its sort of fancy – but am afraid I wont be using it any time soon, if ever.

Project Euler – Problem 4

// June 29th, 2009 // No Comments » // project euler, ruby

Project Euler 4

After a while I had time to play around with Project Euler again.

This is again a pretty straightforward solution. The ruby value from this exercise is that I found ruby does not have increment or decrement operator, which is a departure from C and Java. The argument for this design decision is here.

The only hint I think may be useful for someone just stuck at what looks like a pretty good palindrome is that look at your loop again may be there is a greater number that you never reached because you broke the loop.

By the way, this is a great resource for ruby newbies like me!