C++ program to check PRIME numbers

My previous post was about prime numbers and demonstrated a program to generate them in C++ . This   post is about finding whether a number is prime or not. Now as stated earlier, prime numbers are only divisible by the number 1 and themselves, and we will be using this particular property to find whether a number is prime or not. Please read the post Prime number generation in C++ for more information on prime numbers and how to generate them.

The method is simple, divide the prime number by integers ranging from 2 to number-1. If the division generates a whole number(that is remainder is 0), then it is not a prime number, as they are only divisible by themselves(and 1) and not by any other number.

For e.g if we want to check whether 5 is a prime number or not(which it is :p ), we simply divide 5 by numbers less than 5 i.e 2,3,4 . Since the division will not generate a whole number, hence it is a prime number. In the language of coding, simply run a loop from 2 to number-1 and divide it with the number itself. If the remainder is 0 then it is not a prime no. If it is 1 then it is a prime number. Simple !! :)

The following program demonstrates the above method : 

// Program to check whether a given integer is prime or not

#include <iostream>

#include <iomanip> // for exit() function

int main()

{

     int number;

     bool flag = false;

     // prompts the user to enter a value to test for prime property

     std::cout<<" Enter the number to test : ";

     std::cin>>number;

     if ( number == 2 ) // checks if 2 is entered(as 2 is a prime number )

     {

          std::cout<<" The number is PRIME !!! ";

          exit(true); // terminates the program is two is enterd, as there is no need for further checking

     }

     else // divides the number with value from 2 to (number-1)

     {

          for (int i=2; i<number; i++)

          {

               // if it is divisible than values smaller than number-1 it is non - prime

               if ( number%i == 0)

                    flag = false;

          }

     }

     // prints the correct message based on the flag value

     if ( flag == true )

          std::cout<<" \n The number is NON-PRIME !!!";

     else

          std::cout<<"\n The number is PRIME !!! ";

     return 0;

} //end of main

------ OUTPUT ------

 ------ Some Facts ------

• The only even prime number is 2. All other even numbers can be divided by 2.
• If the sum of a number's digits is a multiple of 3, that number can be divided by 3.
• No prime number greater than 5 ends in a 5. Any number greater than 5 that ends in a 5 can be divided by 5.
• Zero and 1 are not considered prime numbers.
• Except for 0 and 1, a number is either a prime number or a composite number. A composite number is defined as any number, greater than 1, that is not prime.

Please do comment if you don't understand any part or want to know more or just want to say thanks. I love programming and love to teach my friends. Your suggestions and appreciation will make this blog much better.  

------ Related Posts ------

1 - Prime number generation in C++ :  http://programsplusplus.blogspot.in/2012/03/numbers-can-become-quite-huge-mess-when.html

2 - Prime number theorem : http://mathworld.wolfram.com/PrimeNumberTheorem.html
3 - Fibonacci series in C++ : http://programsplusplus.blogspot.in/2012/03/fibonacci-series-in-c.html

 

Prime number generation in C++

Numbers can become quite a huge mess when it comes to generating a particular type of series :p. Many number series such as prime numbers and the famous Fibonacci series are widely taught to C++ beginners. My previous post was related to Fibonacci series so i thought it be a good idea to write something on prime numbers.

Now, for those who don't really know :P, prime numbers are basically numbers that are only divisible by 1 and themselves.
For e.g 23 is a prime number as it is divisible only by 1 and itself. Some prime numbers are as follows :
2 3 5 7 11 13 17 19 23 31 37 41.....so on. Notice that most of the prime numbers greater that 2 are odd. This is also a
notable property of prime numbers.

However, the question is this ...HOW TO GENERATE THEM  ???? It seems that there is no exact formula to generate all the
prime numbers. But by using simple loops , we can generate them in C++. :)  The program given below shows how :

// Program to generate prime numbers in C++

#include <iostream>

int main()
{
     int max;
     // prompts the user to enter the range in which to generate
     std::cout<<" Enter the upper range ? : ";
     std::cin>>max;

     for (int n=2; n<max; n++) // main loop
     {
          int flag = 0;
          // loop to check whether a numbers is prime or not
          for (int i=2; i<=n/2; i++)
               if ( n%i == 0 )
               {
                    flag = 1;
                    break;
               }
               if ( flag == 0 )
               {
                    std::cout<<" "<<n;
               }
     } // end of main loop
     return 0;
} // end of main

------ OUTPUT ------

------ Programming advice and Tips ------

1 - There are numerous ways to generate prime numbers, you can find a lot of algorithms simply use our holy grail of search engines, GOOGLE. !!!

2 - Many algorithms use have different complexity and vary on speed, complexity and limitations. So choose what suits you best.



Please do comment if you don't understand any part or want to know more or just want to say thanks. I love programming and love to teach my friends. Your suggestions and appreciation will make this blog much better. 
 

------ Related Posts ------ 

1 : Fibonacci series in C++ : http://programsplusplus.blogspot.in/2012/03/fibonacci-series-in-c.html 
2 : Sieve of Eratosthenes algorithm to generate prime numbers ( for all programming languages ) : http://rosettacode.org/wiki/Sieve_of_Eratosthenes#C.2B.2B
3 : Prime Number Theorem : http://en.wikipedia.org/wiki/Prime_number_theorem
4 : Checking whether a number is prime or non-prime : http://programsplusplus.blogspot.in/2012/03/c-program-to-check-prime-numbers.html

Fibonacci Series in C++

The Fibonacci series is a very popular series and has many applications in many fields from mathematics to biology.
The series is as follows : 1 1 2 3 5 8 13.....  There are also negafibonacci number series which are have negative value.
Now, observe carefully, we see that each number in the Fibonacci series is the sum of the preceding two number and here
lies the method to generate them using C++. Simply add the two preceeding numbers and store them inside an array.
for e.g to generate 1 1 2 3 5, simply,
add 1,1 --> 1+1 = 2, and store it.
then again add 2,1 --> 2+1 = 3 ,and store it.
and, finally add 3,2 --> 3+1 = 5 ,and store it.
The following program demonstrates the concept.
// Program to print a sequence of fibonacci series
#include <iostream>

int main()
{
     int max,i=0,j=0;
     int temp;
     int arr[50];
     // prompts the user to enter the limit
     std::cout<<" Numbers to generate (max 50) ? : ";
     std::cin>>max;
     // initializes first two indexes with 1
     arr[0] = 1;
     arr[1] = 1;
     for (i=0; i<max; i++)
     {
          temp = arr[i] + arr[i+1];
          j = i+2;
          arr[j] = temp;
     }
     std::cout<<std::endl;
     // to display the fibonacci series
     for (i=0; i<max; i++)
     {
          std::cout<<" "<<arr[i];
     }
     return 0;
} // end of main

There are a numbers of ways to generate Fibonacci series, for more information please visit
http://en.wikipedia.org/wiki/Fibonacci_number

Please do comment if you don't understand any part or want to know more or just want to say thanks. I love programming and love to teach my friends. Your suggestions and appreciation will make this blog much better. 

Factorial program in C++

Calculating factorial is one of the most basic programs in did when i was learning C++ in 12th. :) Its quite a simple program actually, just decrement the number and multiply it with itself. Anyways C++ rookies will find this program on calculating factorial handy, since it is a part of their lab syllabus. The program below calculates the factorial of integers as well as decimal points .

// Program to calculate the factorial of a number
#include<iostream>

int main()
{
     double number;
     double result = 1.0;
     std::cout<<" Enter the number : ";
     std::cin>>number;
     for (double i=number; i>0.0; i--)
     {
          result *= i; // translates to result = result * i;
     }
     std::cout<<"\n The factorial is : "<<result;
     return 0;
} // end of main

------ OUTPUT ------

Please do comment if you don't understand any part or want to know more or just want to say thanks. I love programming and love to teach my friends. Your suggestions and appreciation will make this blog much better.  

Counting number of words in a string

This program is used to find the number of words in a string. Now, to do this is actually very simple.
Simply count the number of spaces between words. To do this, simply traverse the string using a loop and
increment a counter variable whenever a space character occurs. Simple :) .!! Do not forget to initialize the
counter variable !!!
Here is the source code : 

// Program to count the number of words in a string
#include <iostream>

int main()
{
     char string[50];
     int counter = 1;
     // prompts the user to enter a string
     std::cout<<" Enter the string ( max 50chars ) : ";
     std::cin.getline(string,sizeof(string));

     for (int i=0; string[i]!= '\0'; i++ )
     {
          if ( string[i] == ' ' )
               counter++;
     }
     std::cout<<"\n Number of Words are : "<<counter;
     return 0;

} // end of main

------ OUTPUT ------

Please do comment if you don't understand any part or want to know more or just want to say thanks. I love programming and love to teach my friends. Your suggestions and appreciation will make this blog much better.  

------ Related Posts ------

Converting a string to uppercase : http://programsplusplus.blogspot.in/2012/02/converting-array-of-string-to-uppercase.html