# 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

1. Enter the starting number greater than 1 of your set x:
2. Enter the last number of your set y:
3. do while x<=y
4. count=0
5. a= square root of (X)
6. n=2
7. if x<=1
8. print x is not a prime number
9. else if x==2
10. print x is a prime number
11. else
12. do while n<=a
13. if x%n==0
14. count+=1  # equivalent to count=count+1
15. else
16. count+=0
17. end of step 13
18. n+=1
19. end of step 12
20. if count!=0
21. print x is a composite number
22. else print x is a prime number
23. end of step 7
24. x+=1
25. end of step 3

## 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.`