# Write a program to find whether the number is prime or not ??

WAP/ Algorithm or Sudo code to find weather a number is prime or not is the most frequently asked question in interviews and off-course there are too many solutions for this simple question . In this tutorial we will discuss algo to find the prime number from a given set of number.

## What are Prime numbers ??

Prime number is a basic concept of mathematics . Prime numbers are those natural numbers which only can be divided by either 1 or itself. A natural number greater than 1 that are not prime number are known as composite number. For Ex: 5 is a prime number as its divisor are 1 and 5 while 6 is a composite number as it can be divided by 2 and 3 also.

## Concept to find Prime numbers from a given set( S=[x,y] ) of numbers

If you know the concept you can easily write the code in any programming language, that’s why I am explaining the concept find the prime number in an efficient way.

**Concept:** If a number is not divisible by any number below its square root excluding 1, it will not divisible by any number except itself.

So we have to look at only the numbers below the square root in order to check whether a number is prime.

## Algorithm to find prime numbers from a given set( S=[x,y] ) of numbers

- Enter the starting number greater than 1 of your set x:
- Enter the last number of your set y:
- do while x<=y
- count=0
- a= square root of (X)
- n=2
- if x<=1
- print x is not a prime number
- else if x==2
- print x is a prime number
- else
- do while n<=a
- if x%n==0
- count+=1 # equivalent to count=count+1
- else
- count+=0
- end of step 13
- n+=1
- end of step 12
- if count!=0
- print x is a composite number
- else print x is a prime number
- end of step 7
- x+=1
- end of step 3

## SEE ALSO :Step by Step procedure to install RVM , Ruby and Rails on your linux system

## Ruby program to find prime numbers from a given set( S=[x,y] ) of numbers

Below I am writing a program in Ruby programming language to find prime number from a given set( S=[x,y] ) of numbers :

## Ruby program to find prime numbers

puts "Enter the starting number greater than 1 of your set x: " x=gets.to_i puts "Enter the last number of your set y: " y=gets.to_i while x< =y count=0 a=Math.sqrt(x).to_i n=2 if x<=1 puts "Number is not prime , as it is smaller than 1 \n" elsif x==2 puts "2 is a prime number \n" else while n<=a if x%n==0 count+=1 else count+=0 end n+=1 end if count!=0 puts " #{x} is a composite number \n" else puts " #{x} is a prime number \n" end end x+=1 end

Now when you know the concept and algorithm you can easily write program in any other language. I just write here program in **Ruby Programming Language **, if you need it in any other language please mention in comments.

Have something to add or still stuck somewhere ?? share it in comments .

Follow us on Facebook, Google Plus and Twitter.