Determine if a Number is Prime using Sieve of Eratosthenes
The Sieve of Eratosthenes method generates all prime numbers up to a given number n and then checks if the given number is present in the list of primes.
Example: In this example we use the sieve_of_eratosthenes method generates all prime numbers up to n, and then is_prime_sieve checks if the given number n is present in the list of primes.
def is_prime_sieve(n)
return false if n <= 1
primes = sieve_of_eratosthenes(n)
primes.include?(n)
end
def sieve_of_eratosthenes(n)
primes = []
sieve = Array.new(n + 1, true)
sieve[0] = sieve[1] = false
(2..Math.sqrt(n)).each do |i|
next unless sieve[i]
(i * i).step(n, i) { |j| sieve[j] = false }
end
sieve.each_with_index { |is_prime, i| primes << i if is_prime }
primes
end
puts is_prime_sieve(17) # Output: true
puts is_prime_sieve(15) # Output: false
Output
true false
How to Determine if a Number is Prime in Ruby?
In this article, we will discuss how to Determine if a Number is Prime and contains a specific value in ruby. We can determine if a Number is Prime through different methods. Let us study them in detail
Table of Content
- Determine if a Number is Prime using Prime Library Approach
- Determine if a Number is Prime using Loop Approach
- Determine if a Number is Prime using Sieve of Eratosthenes
Contact Us