Skip to content

Instantly share code, notes, and snippets.

@shadabahmed
Created February 25, 2012 03:57
Show Gist options
  • Save shadabahmed/1906311 to your computer and use it in GitHub Desktop.
Save shadabahmed/1906311 to your computer and use it in GitHub Desktop.
Primes - A class for finding upto nth prime .. optimizes by dividing by only already figured out primes
class Primes
# Initialize list of primes with 2
@@primes = [2]
@@current_prime = 1
# Reset the prime number generator
def self.reset
@@current_prime = 1
end
# Get the next prime number in sequence
def self.next
# Iterate the current prime with 1 and keep incrementing until prime is found
@@current_prime += 1
until is_prime?(@@current_prime)
@@current_prime += 1
end
@@primes << @@current_prime
@@current_prime
end
private
# Find a number is prime
def self.is_prime?(num)
# Iteration only required till the root of the number.
# There will be atleast one small factor < sqrt(num) if it is composite
max_num = Math.sqrt(num)
# Iterate over already calculated primes and find if any smaller prime divides the number
@@primes.each do|i|
break if i > max_num
return false if num % i == 0
end
true
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment