Skip to content

Instantly share code, notes, and snippets.

@pjc
Created July 1, 2012 22:44
Show Gist options
  • Save pjc/3029917 to your computer and use it in GitHub Desktop.
Save pjc/3029917 to your computer and use it in GitHub Desktop.
Euler Project in Ruby - Problem 7
def prime? x
(2..x-1).each { |y| return false if x % y == 0 }
true
end
x = 10_001 # We look for 10 001st prime number
n = 3 # Start at 3 so we can skip even numbers
counter = 1 # Counter at 1 because 2 is prime number
while true
counter += 1 if prime? n
break if counter == x
n += 2 # We can skip the odd numbers
end
puts "The answer is #{n}."
# This code takes more than 15s to run, the solution is 104_743
@dinnu93
Copy link

dinnu93 commented Mar 15, 2013

nice solution but has performance issues,taking so long to give the result to rectify that
change def prime? x as follows

def prime? x
a=Math.sqrt(x)
(2..a).each { |y| return false if x % y == 0 }
true
end

Now observe the time difference between the results by ur algo and my algo

@ignazioc
Copy link

ignazioc commented Apr 3, 2013

i think there is another performance increment that can be done.
We have all primes number smallest than x, so we can check only if x is divisible by one of this.

This is my code

def isPrime?(value, array)
array.each do | x |
return false if value % x == 0
end
return true
end

puts ''
primes = Array.new
startvalue = 2
while (primes.count < 10001)
primes << startvalue if isPrime?(startvalue, primes)
startvalue = startvalue + 1
end
puts primes[-1]

@yatish27
Copy link

yatish27 commented Jul 1, 2014

@ignazioc Using the previous primes increases complexity

@schinsue
Copy link

Why don't you use the library ruby provides you with?

require 'Prime'

puts Prime.instance.first(10_001).last

@wb4r
Copy link

wb4r commented Jul 31, 2015

Just remember to write 'Prime' with lowercase => require 'prime'

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment