How to Implement Prime Number Check Algorithm Using a C++ Program Example

by Koscica Dusko on March 13, 2014

The set {1, 2, 3, …} is known as the set of natural numbers, they are usually signed as N numbers.

This tutorial is about prime numbers. So what are prime numbers?

Let us take number 15, which could be represented as shown below. This is not a prime number.
15 = 1 * 3 * 5
;
Let us take number 13, which could be represented as shown below. This is a prime number.
13 = 1 * 13

In case of number 13, you will not be able to find any natural numbers beside 1 and 13 that will divide number 13 without some left over.

What do we mean by left over? Let us take number 17, and if you divide 17 with 7, you could represent 17 as shown below. The left over is 3 in this case.
17 = 7 *2 + 3.

The following is the list of few primer numbers and it is sometimes noted as P set.
{2, 3, 5, 7, 11, 13, …}

One more thing, the numbers 5 and 7 are the twin primes, they are represented like: 6n – 1 and 6n + 1. This time n is equal to 1.

All prime numbers are represented in that way, if they are bigger than 3. But all numbers of 6n+1 or 6n-1 type are not prime numbers.

Last number that could be candidate to make tested number not prime, is not bigger than sqrt(n).

Also one very important fact about prime number is that 1 is not prime number.

Prime Number Checker Program

The following C++ example code will check whether the given number is a prime number or not.

#include <iostream>
#include <cmath>

using namespace std;

bool IsPrime (int);

int
main(void)
{

cout<<"The program checks if the given number is prime!"<<endl;
for(int i= 0; i<=44; i++, cout<<'_'); 
cout<<endl;

do
{
  cout<<"Do you wish to test next number y/n->";
  char cRespond;
  cin>>cRespond;

  if ((cRespond == 'y')||(cRespond == 'Y'))
  {
  	cout<<"Enter the number:->";
  	int myInput;
  	cin>> myInput;

    (IsPrime(myInput)==true)? cout<<"It is":cout<<"It is not";
    cout<<" prime number!"<<endl;

  	continue;
  }
  break;
}
while(true);

return EXIT_SUCCESS;
}

bool 
IsPrime (int n)
{
  if((n==2)||(n==3)) return true;

  int iResidum = n % 6;
  if(!((iResidum == 5) || ( iResidum == 1))) return false;

  if(n %3 == 0) return false;
  for(int i=1; 
      6*i <= (int)sqrt(double(n))+6; 
      i++)
  {
      if( n % 6*i-1==0) return false;
                if( n % 6*i+1==0) return false;
  }

  return true;
}

Explanation of the Algorithm

First we will analyse the main function and then we will go in IsPrime() function.

The main program does the following:

  1. Write the header where we explain what we do in this program.
  2. We create “do wile” circle that will enter the numbers to be examined.
  3. We ask the user should we stop testing the numbers or should we continue with the testing.
  4. If the respond is y or Y, we will test the next number with function IsPrime, otherwise we stop with the checking.
  5. If the logical function returns the true we print message that the number is prime, but if the function returns false we print the message that the number is not a prime number.

The function does the following:

  1. Test if the number is: 2 or 3, because they are not of 6n+1 or 6n-1 form.
  2. We divide the potentially prime number with 6, and if we get remain that is different than 5 or 1 we don’t have potentially prime number. The function returns false.
  3. In the “for” we test all potentially prime numbers. If they could be disassembled into composite numbers then those numbers will be of 6n+1 or 6n-1 form. We will have few tests that are not necessary but if one wishes it could find those numbers in the list of prime numbers that would be constructed. That way, those tests would be meaningless. Think why.
  4. The last potentially divisor is not greater than sqrt(n) +6. Aldo, I am not sure is it possible to use just sqrt(n).

The above approach is not bad for smaller numbers, but when the number that we are checking becomes to big it could slow down the program. Also, there is one more trick, to generate accidental numbers and divide the candidate number with those numbers, but this way we will not get number that is prime for sure. To benefit from this approach we could insert this before “ for” in the function. That could sometimes catch the numbers that are not prime numbers.

One more idea is to create the list of prime numbers and search is the number in the list. Also, if you really like to create the faster solution, you could keep the numbers in some data structure that could outperform simple vector in this problem.

Additional Exercises

  1. Try to enlist all prime numbers smaller than the given one.
  2. Print all prime numbers in range [a..b], where a is less than b.
  3. Use Sieve of Eratosthenes to list all prime numbers smaller than n.
  4. Find the prime numbers that will divide n without the left over.
  5. Find how many prime numbers divide n without left over and how many divide n with left over.
  6. Check is the pair of numbers: 6*i + 1 or 6*i -1 for some i couple of prime numbers.
  7. Break the number n into sum of prime numbers, if possible.
    • The prime numbers will not include 1.
    • The prime numbers will include 1.
    • Any prime number will be used only once.
    • The prime numbers could be used more times.
    • The prime numbers are the biggest prime numbers that could break the number into the sum of prime numbers that will use only once each prime number, or use the prime numbers more times.

Linux Sysadmin Course Linux provides several powerful administrative tools and utilities which will help you to manage your systems effectively. If you don’t know what these tools are and how to use them, you could be spending lot of time trying to perform even the basic administrative tasks. The focus of this course is to help you understand system administration tools, which will help you to become an effective Linux system administrator.
Get the Linux Sysadmin Course Now!

If you enjoyed this article, you might also like..

  1. 50 Linux Sysadmin Tutorials
  2. 50 Most Frequently Used Linux Commands (With Examples)
  3. Top 25 Best Linux Performance Monitoring and Debugging Tools
  4. Mommy, I found it! – 15 Practical Linux Find Command Examples
  5. Linux 101 Hacks 2nd Edition eBook Linux 101 Hacks Book

Bash 101 Hacks Book Sed and Awk 101 Hacks Book Nagios Core 3 Book Vim 101 Hacks Book

{ 14 comments… read them below or add one }

1 Lev Lafayette March 14, 2014 at 1:03 am

Interesting results. :)

lev@owl ~/Desktop $ ./prime
The program checks if the given number is prime!
_____________________________________________
Do you wish to test next number y/n->y
Enter the number:->2
It is prime number!
Do you wish to test next number y/n->y
Enter the number:->3
It is prime number!
Do you wish to test next number y/n->y
Enter the number:->5
It is prime number!
Do you wish to test next number y/n->y
Enter the number:->7
It is not prime number!
Do you wish to test next number y/n->y
Enter the number:->11
It is prime number!
Do you wish to test next number y/n->y
Enter the number:->13
It is not prime number!
Do you wish to test next number y/n->y
Enter the number:->17
It is prime number!
Do you wish to test next number y/n->y
Enter the number:->19
It is not prime number!
Do you wish to test next number y/n->y
Enter the number:->23
It is prime number!

2 Gurudutt March 14, 2014 at 1:51 am

So, this program does not work is it?

3 duskoKoscica March 14, 2014 at 2:37 am

Ok, “interesting” , it looks like iResidum and the if that goes with it should be adjusted, so if the residum is in { 0, 2, 3, 4} the number is not prime for sure!

4 duskoKoscica March 14, 2014 at 3:08 am

To solve this there are at least two possible solutions> you could code somthing like this if( iResidue==0) or ( iResidue==2) or (iResidue ==3) or (iResidue==4)) return false with iso646 or iso464, or you could use if((iResidue==1) or (iResidue==5)) the code that checks is the number prime} else { return false;} . But ther is few more things to improve!

5 Ron March 14, 2014 at 7:10 am

Interesting article.

using c++ , object oriented language, and coding in as a procedural language like ‘C’ or perl should be considered as a crime.

Many new developers visiting the site will pick up bad habits and then again all code should be written so that it could be easily unit tested.
I have seen many such articles are written where the author writes articles to hon their language skills without keep bigger picture in mind.

Keeping that in mind the subject is quite informative.

Thanks.
Ron.

6 duskoKoscica March 14, 2014 at 8:20 am

So with bigger picture in mind, try to see how would you handle this, the task for more advanced, this is like you wanna use friend function or how, I would like to hear more about idea you have in mind.

7 Ron March 14, 2014 at 8:35 am

duskoKoscica,
this is what I’d suggest.
Create a class().
add methods(), keeping each method smaller and simpler for testablity.
reduce cyclomatic complexity.
Write in an object oriented manner.

8 duskoKoscica March 14, 2014 at 10:53 am

Ok now I know how would I do it but I would like to see how would you do it!

By the way, happy Pi day, if that thing is not a joke, it seams cool!

For further studies I would recomend that you wisit the wikipedia and find more about the prime numbwers and yes there is one very interesting site about prime numbere of different form. There are, also the sites where you should find some algorithms that work better with certain types of prime numbers, tha algorrithmes that count how manny prime numbers there are etc..

9 DirkM March 15, 2014 at 3:18 am

Boring! Prime numbers in this way? It is a subject of no practical mening at all!

10 duskoKoscica March 17, 2014 at 8:02 am

I have had some time on this week to look more carefully in those functions and there are few more corrections. Also, I need to say that I am not happiest how it looks like, but it was tested till 10, 100, 1000. Now I need to say that it should be inspected more carefully but that is up to reader.
Those who like to fix the things have had enough time, so now for those who could not fix it on they own!
bool
IsPrime( unsigned long long n)
{
if((n==2)||(n==3)) return true;

int iResidum = n%6;
if((iResidum==0)||(iResidum==2)||(iResidum==3)||(iResidum==4)) return false;

for(unsigned long long i =1;
6*i <= sqrt(i) +1;
++i)
{
if(n%(6*i-1)==0) return false;
if(n%(6*i+1)==0) return false;
}
return true;
}

If some of you have noticed some errors, THX a lot!

11 Mike March 21, 2014 at 3:59 am

I don’t know why DirkM said that.
My teacher said that prime numbers are important!
I don’t know why! But he said Ok to.

12 Ana March 22, 2014 at 4:25 am

DirkM you never listen to techer and all you have are those storyies that you don’t like something or somethig like that.
Me, Miranda, Johanna and Betty don’t like you.
You should liten to techer, ana pay more attention to subjects.
Next when you say something like that in class I will tell you off.

13 duskoKoscica April 3, 2014 at 11:58 pm

To checke if the big number is prime number there are algorithms like: Polard-Rool, Dickson, and few other methods that are known to common people and few that are not. There are few forms of prime numbers, ok a lot of forms of prime numbers, and also one could even get the money revord if has success in finding bigest prime. This prime numbers are never ending story, it is not like Fermat big theorem, when they solve the thing after long time and that’s it. Prime numbers are always in.

14 duskoKoscica December 1, 2014 at 6:33 am

There are some other forms of prime numbers like 6n+1 and 6n+5, it would be nice to find few conditions that would tell you very fast if the number is prime or not, that way you would not need to divide numbers.
Yes there are some ways to say if certain type of prime number is prime to.,

Leave a Comment

Previous post:

Next post: