The Intrique of Prime Numbers | Detailed Explanation for C++ Kids
Prime numbers are tricky to spot.
A number that looks like a prime may in fact be a multiple of a smaller prime number.
In this math programming tutorial for kids, we explore how C++ can be used to verify prime numbers efficiently.
So let's see how to know for sure that a number is a prime in C++.
Of-course there is only one way:
Understanding Prime Number Logic in C++
A prime number is one that can only be divided by itself and one (1).
Let's try to draft a C++ algorithm that checks prime numbers, with the number 97 in consideration.
To know for sure whether it is a prime number, we will
recursively (repetitively) divide it by every number between
2 and 96 (97 minus 1).
If none of these divisors gives a remainder of zero, then 97
is certainly a prime number.
Create a new C++ class file;
Call it CheckPrime.
Type out the adjoining C++ code for checking for primeness.
Base Theory of Quick-Check for Primeness in C++
Since the world is always in a hurry, we can make use of a
little extra speed.
This C++ code example shows how to check if a number is prime using a fast algorithm based on complementary factors.
Consider the number 36; Its factors are:
Every factor of 36, when arranged in ascending or descending order, can be divided into 2 equal parts at the position of its square-root.
It is easily seen that every factor of 36 on one side of the divide has a complementary factor on the other side.
Hence, we can search for only a particular group of factors, (preferably the more compact group, i.e, between 1 and √36) to see if 36 has any factors.
A fast Check for Primeness in C++
So for our quick prime number check C++ algorithm, we will use the range of
2 to √number.
Type out the adjoining C++ code for fast prime number check.
Note: You can simply tweak the existing function from the previous exercise.
You can comment out the C++ code for the main class
from the previous lesson if you have been following.
So! C++ Fun Practice Exercise - Check Prime Number
As a fun practice exercise, feel free to try out your own numbers, and see how the C++ code checks the numbers to ascertain which ones are prime numbers.
C++ Code for Checking Prime - Header File.
#include <iostream>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
class CheckPrime {
public:
CheckPrime(unsigned);
virtual ~CheckPrime();
string verifyPrime(void);
private:
unsigned int prime_suspect; // We suspect that this number is prime
double square_root; // this variable is a helping one.
unsigned int test_range; // range for minimal looping
string result;
stringstream aux;
};
C++ Code for Checking Prime - Class File.
#include "CheckPrime.h"
CheckPrime::CheckPrime(unsigned val) {
result = "";
prime_suspect = val;
square_root = sqrt(prime_suspect); // Get square root
test_range = (int)ceil(square_root); // Extract an absolute value
}
/**
* Does the actual evaluation to see if our number is prime.
* @param - Takes no parameters
* @return - String (Resolve to check.)
*/
string CheckPrime::verifyPrime() {
aux.str(""); // Clear int to string object
aux << prime_suspect;
// prime_suspect is a prime number until proven otherwise
result = "Prime State:\n" + aux.str() + " is a prime number.";
/* Loop through searching for factors. */
for (unsigned i = 2; i < prime_suspect; i++) {
if ((prime_suspect % i) == 0) {
result = "Prime State:\n";
result += aux.str() + " is not a prime number.\n";
result += "At least one factor of " + aux.str();
aux.str("");
aux << i;
result += " is " + aux.str();
break;
}
}
// If no factor is found:
return result;
}
CheckPrime::~CheckPrime() {
}
C++ Code for Checking Prime - Main Class.
//
#include "stdafx.h"
#include "CheckPrime.h"
#include <iostream>
using namespace std;
int main() {
try {
cout << "\n Welcome to our demonstration sequels\n";
cout << "Hope you enjoy (and follow) the lessons.\n\n";
unsigned int start = 1, stop = 100;
/*
* Use the CheckPrime class.
*/
CheckPrime answer(98);
cout << "\n\n" << answer.verifyPrime() << "\n";
} catch (exception& e) {
cout << "\n" << e.what() << "\n";
}
return 0;
}
C++ Code for Checking Prime Fast - Header File.
#include <iostream>
#include <math.h>
#include <string>
#include <sstream>
using namespace std;
class CheckPrime {
public:
CheckPrime(unsigned);
virtual ~CheckPrime();
string verifyPrime(void);
private:
unsigned int prime_suspect; // We suspect that this number is prime
double square_root; // this variable is a helping one.
unsigned int test_range; // range for minimal looping
string result;
stringstream aux;
};
C++ Code for Checking Prime Fast - Class File
#include "CheckPrimeFast.h"
CheckPrimeFast::CheckPrimeFast(unsigned val)
{
result = "";
prime_suspect = val;
square_root = sqrt(prime_suspect); // Get square root
test_range = (int)ceil(square_root); // Extract an absolute value
}
/**
* Fast copy.
* @param - Takes no parameters
* @return - String (Resolve to check.)
*/
string CheckPrimeFast::verifyPrimeFast() {
aux.str("");
aux << prime_suspect;
result = "Prime State:\n" + aux.str() + " is a prime number.";
/* Loop through a small range searching for factors. */
for (int i = 2; i < test_range; i++) {
if ((prime_suspect % i) == 0) {
result = "Prime State:\n";
result += aux.str() + " is not a prime number.\n";
result += "At least one factor of " + aux.str();
aux.str("");
aux << i;
result += " is " + aux.str();
break;
}
}
// If no factor is found:
return result;
}
CheckPrimeFast::~CheckPrimeFast()
{
}
C++ Code for Checking Prime Fast - Main Class.
//
#include "stdafx.h"
#include "CheckPrimeFast.h"
#include <iostream>
using namespace std;
int main() {
try {
cout << "\n Welcome to our demonstration sequels\n";
cout << "Hope you enjoy (and follow) the lessons.\n\n";
unsigned int start = 1, stop = 100;
/*
* Use the Test Prime class.
*/
CheckPrimeFast answer(98);
// Try the fast version
cout << "\n" << answer.verifyPrimeFast() << "\n";
} catch (exception& e) {
cout << "\n" << e.what() << "\n";
}
return 0;
}