Copyright © Programs ++
Design by Dzignine
Wednesday, 4 April 2012

Sophie Germain Prime Numbers in C++

Prime numbers are those numbers that are only divisible by 1 and themselves. Sophie geramin prime numbers are a special category of prime numbers.
By definition, a prime number, say 'p', is a sophie germain prime number if p is prime and 2p+1 is also prime. For e.g 23 is a sophie germain prime because
23 is prime and 23*2 + 1 = 47 is also prime.

For those who do not know how to check whether a number is prime or not, please read my post : Checking PRIME numbers in C++.

Now generating sophie germain primes, is actually quite a simple task. We need just need to check the following :
1 - p is prime
2 - 2p+1 is prime
3 - print p if both cases 1 and 2 turn out to be true.

The following program generates sophie germain primes upto the limit specified by the user. Please have a look at the source code to have a better
understanding of how the program works. Please leave a comment if you want to ask something or just want to say hi .

// Program to generate sophie germain prime numbers

#include <iostream>

bool checkPrime(int number)
{
     bool flag = true;
     if ( number == 2 ) // checks if 2 is entered(as 2 is a prime number )
     {
      //    std::cout<<" The number is PRIME !!! ";
          return 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;
          }
     }
     return flag; // returns either true or false as the result

}

int main()
{
     int max,i = 2;
     // prompts the user to enter the max numbers to generate
     std::cout<<" Enter the max. numbers to generate : ";
     std::cin>>max;
     int counter = 1;

     while ( counter <= max) // run until the limit is reached
     {
          if ( checkPrime(i) == true ) // initial check to see if p is prime
          {
               if ( checkPrime((2*i) + 1) == true ) // secondary check to see if 2p+1 is prime
               {
                    std::cout<<" "<<i; // displays the number if it turns out to be a sophie germain prime
                    counter++;
               }
          }
          i++;
     } // end of while
     std::cout<<"\n End of program !! ";
     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 ------
1 : For more information on sophie germain primes , please visit : http://en.wikipedia.org/wiki/Sophie_Germain_prime
3 : Generating Prime numbers in C++ : http://programsplusplus.blogspot.in/2012/03/numbers-can-become-quite-huge-mess-when.html

4 comments:

  1. hey check this new website www.countcode.com. It's a social network made for programmers, where you can download,share or upload source codes, where you can count your own code lines for free. You have access to the web forum and the web chatroom. we are happy to have you joined to our community!

    ReplyDelete
  2. Prime number program in C++

    prime number is only divisible by 1 and itself,
    we can easily write prime number program in c++, just check number is not divisible by any other numbers except 1 and number itself.

    ReplyDelete
  3. This code is frequently ask in any examination Prime number program in C++ is very simple and easy to write. Using for loop and if else we can write this code.

    ReplyDelete
  4. A prime number is a whole number greater than 1, which is only divisible by 1 and itself. First few prime numbers are : 2 3 5 7 11 13 17 19 23
    2 is the only even Prime number. Prime number program in C++. Every prime number can represented in form of 6n+1 or 6n-1, where n is natural number. 2, 3 are only two consecutive natural numbers which are prime too.

    ReplyDelete

Comment Here....