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

Selection sort in C++

One family of internal sorting algorithms is selection sort. The basic idea of selection sort is to repeatedly select the smallest key in the remaining unsorted array. Simply put, an element is taken as the smallest key element
and then it is compared with the other elements to sort the array.  It is implemented in the form of exchange selection sort that requires a single array to work with. In this technique, computer keeps on finding the next smallest element and brings it at its appropriate positions.
Selection sort can be used to sort an array in both ascending as well as descending order. The following program demonstrates
the implementation of selection sort in ascending order :

// Program to implement selection sort in C++ ( ascending order )

#include <iostream>

void selectionSort(int AR[],int size)
{
     int i,j,temp;
     for (i=0; i<size; i++)
     {
          for (j=i+1; j<=size; j++)
          {
               if ( AR[i] > AR[j] ) // sorts in ascending order
               {
                    temp = AR[j];
                    AR[j] = AR[i];
                    AR[i] = temp;
               }
          } // end of sub loop
     } // end of main loop

} // end of function selectionSort

int main()
{
     int arr[20],size;
     // prompts the user to enter the elements in the array
     std::cout<<" Enter the no. of elements that you want to enter (max 20 ) : ";
     std::cin>>size;
     std::cout<<" Now enter the elements in the array ";
     for (int i=0; i<size; i++)
     {
          std::cout<<" \n Element "<<i<<" : ";
          std::cin>>arr[i];
     }
     selectionSort(arr,size); // calls the function to sort the array
     std::cout<<" \n The sorted array is as follows ";
     for (int i=0; i<size; i++)
     {
          std::cout<<" \n Element "<<i<<" : "<<arr[i];
     }
     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 ------
Bubble Sort in C++ : http://programsplusplus.blogspot.in/2012/02/bubble-sort-in-c.html
Insertion Sort in C++ : http://programsplusplus.blogspot.in/2012/02/insertion-sort-in-c.html

Insertion sort in C++

Insertion sort is another sorting technique used when sorting arrays. Unlike bubble sort, it uses much less number of passes to sort an array. As the name suggests, sorting is done by inserting elements in their proper order by comparing an element with the elements on either side. Hers is how it works. Suppose we want to sort an array A with elements A[1],A[2]....A[N]. Then,
Step 1 : A[1] by itself is trivially sorted.
Step 2 : A[2] is inserted either before or after A[1] so that A[1],A[2] are sorted.
Step 3 : A[3] is inserted into proper place in A[1],A[2],that is, before A[1], between A[1]
and A[2, or after A[2], so that A[1],A[2],A[3] is sorted.
The process keeps repeating until the array is fully sorted.

The following program demonstrates the use of insertion sort by sorting an array of integers in ascending order

// Program to implement insertion sort ( ascending order )
#include <iostream>

void Insertion_sort(int AR[],int n)
{
     int temp,j;
     AR[0] = INT_MIN;
     for (int i=1; i<=n; i++)
     {
          temp = AR[i];
          j = i-1;
          while ( temp < AR[j])
          {
               AR[j+1] = AR[j];
               j--;
          }
          AR[j+1] = temp;
     } // end of for loop
} // end of insertion sort function

int main()
{
     int arr[20];
     int size;
     std::cout<<" Enter the maximum no. of elements you want (max 20) : ";
     std::cin>>size;
     std::cout<<"\n Now enter the elements in the array \n ";
     // loop to prompt the user to enter the elements in the array
     // notice that the elements are inserted fromt he 1st index rather that 0, as 0 index will be assigned 
     // INT_MIN value from which other elements will be compared
     for (int i=1; i<=size; i++)
     {
          std::cout<<"Element "<<i<<" : ";
          std::cin>>arr[i];
     }
     Insertion_sort(arr,size);
     // as arrays are passed with reference, hence any changes will be reflected in the original array as well
     std::cout<<" \n The sorted array is as follows \n ";
     for (int i=1; i<=size; i++)
     {
          std::cout<<" \n Element "<<i<<" : "<<arr[i];
     }
     return 0;
} // end of main
------ OUTPUT ------

------Programming Advice and Tips------

1 - Even though insertion sort uses considerably less number of passes to sort an array, it still is not useful

when sorting arrays that contain large number of elements. Hence it is best advised to use insertion sort

where the no of elements to be sorted are less(i.e having small value of N).

2 - Notice that all the loops start from index location 1 rather than starting from 0 (which is usually done). This is done because, at the 0th index location, INT_MIN value is stored from which other elements are compared and is vital in terminating the while loop.

3 - INT_MIN is the MINIMUM value that an integer can have. It is usually a negative value, and varies from platform to platform.

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 ------

Bubble Sort in C++ : http://programsplusplus.blogspot.in/2012/02/bubble-sort-in-c.html
Selection Sort in C++ : http://programsplusplus.blogspot.in/2012/02/selection-sort-in-c.html

Converting an array of string to uppercase

Here is a program to convert an array of string into uppercase. Just like a recent post : "lowercase to uppercase" the following program also uses the standard C++ functions such as toupper() to convert string from lowercase to uppercase.

Now, the process is the same as converting a single string, traversing the entire string  using a loop and converting each
character from lowercase to uppercase(or vice-verse) using toupper() (or tolower() ) and storing the converted characters
into another string.

The only difference that comes in an array of strings is that a loop has to be used to process individual strings sorted in the
array.Consider the string as columns of students in a classroom with each of the student sitting in the front desk as the
starting index of that column.

NOTE : be sure to add a terminating null character ('\0') at the end of each converted string, as this is not done by default by the
toupper() function !!!! :O

Here is an sample program.

// Program to convert an array of string to uppercase

#include <iostream>
#include <cctype>

int main()
{
     char name[5][20];
     char temp[5][20];
     int size;
     // prompts the user to enter the no. of string he/she wants in the array
     std::cout<<" Enter the no. of names you want to insert (max 5 ) : ";
     std::cin>>size;
     std::cin.ignore(); // to clear the memory buffer
     std::cout<<" \n Now enter the names (max 20 characters long ) : \n ";
     for (int i=0; i<size; i++)
     {
          std::cout<<" Name "<<i<<" : ";
          std::cin.getline(name[i],sizeof(name[i]));
     }
     // to convert them into uppercase
     int j=0;

     for (int i=0; i<size; i++) // main loop to traverse the rows
     {
          for (j=0; name[i][j] != '\0'; j++) // sub loop to traverse the individual strings
          {
               temp[i][j] = toupper(name[i][j]); // converts each character to uppercase
          }
          temp[i][j] = '\0'; // adds a terminating null character at the end of each string

     }
     // to show the names in uppercase

     for (int i=0; i<size; i++)
     {
          std::cout<<"\n NAME "<<i<<" : "<<temp[i];
     }
     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 ------ 
Lowercase to Uppercsae : http://programsplusplus.blogspot.in/2012/01/lowercase-to-uppercase.html

Uppercase to Lowercase : http://programsplusplus.blogspot.in/2012/01/uppercase-to-lowercase.html