Program to find prime numbers from a set of numbers

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

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.

NO COMMENTS