usingMaths.com
From Theory to Practice - Math You Can Use.







<< PreviousNext >>

How to Code Prime Number Algorithms in C++ - Fun Students Activity



Randomness of Prime Numbers | Maths Explanation for C++ Kids

Prime numbers are natural numbers greater than 1 with no positive divisors other than 1 and itself. Prime numbers, in ascending order, are:

2, 3, 5, 7, 11, 13, 17, 19, 23, ...

Because prime numbers are so random in their progression, they are very difficult to predict as they get larger.
For the reason of their unpredictability, prime number are applied in

  • Cryptography: RSA encryption relies on large prime numbers.
  • Hashing: Prime numbers help reduce collisions in hash functions.
  • Data structures: Primes are used in sizing hash tables and optimizing algorithms.

In this beginner-friendly Maths C++ tutorial for kids, we'll show how to list prime numbers in a fun and interactive way for STEM students.
Writing code in C++ to list prime numbers will involve checking every number in a range of interest and gathering those that are without factors.



Logic for Determining Prime Numbers | Detailed Explanation for C++ Kids

Say we want to implement a C++ algorithm to list all prime numbers between 2 and 100 inclusive, we would start from 2; check to see whether it has any factors; keep it as a prime number if it has no factors; otherwise discard it.
We would then go to 3, and repeat the same process.
Repeat same for 4, 5, 6, 7, ..., 98, 99, 100.

But we can always use a few tricks for the C++ algorithm...

We will take the following steps:
Step 1:

First, we'll start our range from 9 (keeping 2, 3, 5, and 7 as prime numbers).

Step 2:

Next, we'll only check through odd numbers.

Step 3:

Next, we'll check against the factors 2, 3, and 5.

Step 4:

Lastly, we'll check with a subset of smaller prime numbers that we'll gather as our check progresses.


Create a new C++ class file;
Call it PrimeNumbers.

Type out the adjoining C++ code for listing prime numbers.



Note: 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 - List Prime Numbers

As a fun practice exercise, feel free to try out your own boundary values, and see how the C++ code lists the prime numbers between those boundary values.







C++ Code for Prime Numbers - Header File.

#pragma once

#include <iostream>
#include <vector>
#include <string>
#include <sstream>
#include <math.h>

using namespace std;

class PrimeNumbers {
public:
    PrimeNumbers(unsigned, unsigned);
    virtual ~PrimeNumbers();
    string getPrimes();
private:
    vector<unsigned> list_of_primes; // We will house our gathered prime numbers here.
    unsigned int start; // Where to start.
    unsigned int stop; // Where to stop.
    unsigned int progress; // progress report
    unsigned int index; // index into array list_of_primes
    double square_root; // Our loop range for speed enhancement
    bool do_next_iteration;
    string result;
    stringstream aux;

};


C++ Code for Prime Numbers - Class File.

#include "stdafx.h"
#include "PrimeNumbers.h"


PrimeNumbers::PrimeNumbers(unsigned first, unsigned last) {
    start = first;
    stop = last;
    // STEP 1:
    progress = 9;

    list_of_primes = { 2, 3, 5, 7 };

    square_root = 0;
}

/**
* Garners the prime numbers between the requested range.
* @param - Nil
*/
string PrimeNumbers::getPrimes() {
    // STEP 2:
    for (; progress < stop; progress += 2) {
        
        do_next_iteration = false; // a flag

        // STEPS 3, 4:
        // Check through already accumulated prime numbers
        // to see if any is a factor of "progress".
        square_root = (int)ceil(sqrt(progress));

        index = 0;
        for (; list_of_primes[index] <= square_root; index++) {
            if ((progress % list_of_primes[index]) == 0) {
                do_next_iteration = true;
                break;
            }
        }
        if (do_next_iteration) {
            continue;
        }

        // if all checks are scaled,then "progress" is our guy.
        list_of_primes.push_back(progress);
    }

    list_of_primes.shrink_to_fit(); // not altogether necessary

    // Display result.
    aux << start;
    result = "The set of prime numbers between " + aux.str() + " and ";
    aux.str("");
    aux << stop;
    result += aux.str() + " are: \n";

    for (unsigned n : list_of_primes) {
        aux.str("");
        aux << n;
        result += aux.str() + "; ";
    }
    return result;
}


PrimeNumbers::~PrimeNumbers() {
}

C++ Code for Prime Numbers - Main class.

// Arithmetic.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "PrimeNumbers.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;

        /*
        * List of Prime Numbers.
        */
        PrimeNumbers p_list(start, stop);
        cout << "\n\n" << p_list.getPrimes() << "\n";

    }    catch (exception& e) {
        cout << "\n" << e.what() << "\n";
    }
    return 0;
}




<< PreviousNext >>