WELCOME
Good time of the day, dear friends, coders and enthusiasts.
I haven't been posting for a long while, and have been primarily improving myself and working on some side projects. But the will to share what I have been learning and doing is still in me, burning wildly.
I have decided to start sharing some small articles about algorithms, and I decided to start from small.
Today we are going to look through an algorithm that checks whether the provided number is prime.
What is a prime number ?
Before getting into writing the code, let us understand what exactly the prime numbers are? Prime numbers are those numbers which can only be divisible by itself or 1. So, we will design a code which can fulfill the property of prime numbers.
That means, if the number is less than 2, we can immediately return 'false'.
Steps to reproduce
Return false if the provided number is less than 2 (because 0 and 1 are not considered to be prime numbers)
Run through all the numbers starting from 2 till 'n-1', where 'n' is a number provided as a parameter, and check whether 'n' is divisible by any of them
If we find that 'n' is divisible by any number in the range [2...n-1], then immediately break the loop and return 'false'
If we did not return a result in step 3, then return true. That means the number is prime
Code
If you want an immediate solution, you can use 'prime?' method provided by Ruby.
# Pre-defined class
require 'prime'
# Initializing the numbers
num1 = 17
num2 = 90
num3 = 29
# Printing if prime or not
puts num1.prime? # true
puts num2.prime? # false
puts num3.prime? # true
Ruby even provides a method for listing all prime numbers in a specified range
require 'prime'
Prime.each(27) do |prime|
p prime
end
#=> 2, 3, 5, 7, 11, 13, 17, 19, 23
Ruby solution - 1
Here's the actual solution to check whether the number is prime, with Ruby. Of course, assuming that the input number is positive.
def is_prime(num)
return false if (num < 2)
(2..(num - 1)).each do |n|
return false if num % n == 0
end
true
end
Ruby solution - 2
And if you want it shorter, as a one liner, here's the one that returns the result faster. Because it does not check all numbers in the range of [2...n-1], it only checks the numbers between [2...sqrt(n)].
It is considered that there are no divisors of a number higher than it's square root. So we are only checking numbers till square root of 'n'.
def is_prime?(num)
return false if num < 2
Math.sqrt(num)
.to_i
.downto(2)
.each {|i| return false if num % i == 0}
true
Solution provided above is one of the most optimal ones. Otherwise you can also check numbers between [2...n/2], that is till the half of the provided number. But of course, square root provides us with even less numbers to run through.
Javascript solution - one liner
Here you can see almost the same solution as provided in 'Ruby solution - 2', but in Javascript.
const isPrime = num => (num > 1) && Array(Math.floor(Math.sqrt(num)) - 1).fill(0).map((_, i) => i + 2).every(i => num % i !== 0);
This solution checks whether none of the numbers between [2...sqrt(n)] are divisible by 'n'. If it finds any divisor in that region, it returns false.
Conclusion
So, this is it, guys. Hope you gained some useful insights from this post or at least were happy to see beautiful one liner code snippets in Ruby and Javascript.
I will try to keep posting other useful solutions to common simple algorithms, so stay with Dev.to and all the developer community to keep improving.
Stay safe and Good luck!!!
Oldest comments (0)