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:
- Write the header where we explain what we do in this program.
- We create “do wile” circle that will enter the numbers to be examined.
- We ask the user should we stop testing the numbers or should we continue with the testing.
- If the respond is y or Y, we will test the next number with function IsPrime, otherwise we stop with the checking.
- 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:
- Test if the number is: 2 or 3, because they are not of 6n+1 or 6n-1 form.
- 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.
- 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.
- 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
- Try to enlist all prime numbers smaller than the given one.
- Print all prime numbers in range [a..b], where a is less than b.
- Use Sieve of Eratosthenes to list all prime numbers smaller than n.
- Find the prime numbers that will divide n without the left over.
- Find how many prime numbers divide n without left over and how many divide n with left over.
- Check is the pair of numbers: 6*i + 1 or 6*i -1 for some i couple of prime numbers.
- 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.
My name is Ramesh Natarajan. I will be posting instruction guides, how-to, troubleshooting tips and tricks on Linux, database, hardware, security and web. My focus is to write articles that will either teach you or help you resolve a problem. Read more about
Comments on this entry are closed.
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!
So, this program does not work is it?
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!
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!
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.
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.
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.
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..
Boring! Prime numbers in this way? It is a subject of no practical mening at all!
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!
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.
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.
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.
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.,
all algorithms are buggy!
I have tested the 500th prime which should be 3557 according to Wikipedia ( http://en.wikipedia.org/wiki/List_of_prime_numbers#The_first_500_prime_numbers ).
There are a lot of multiple of 5 declared as primes!
I have presently no time to look after the errors..
@Alain
Hi!
First, I will notice that this function is created for single testing, rather than for range of tests, this argument would be obvious from performance point of view, however it could be modified for that purpose as well. In OOP it would be nice to have…
Second, if you could figure out that there is a problem with numbers that are multiples of five, I am sure that you would be able to figure out how to exclude them as well.
It would be interesting to find what did cause that problem.
Zero, this is a blog.
THX, for noticing this and contributing to quality of this article!