Prime Numbers with C++ - How to Find Out

In this tutorial, we will unravel the prime numbers. We'll learn how to check whether a number is prime or not, and how to display a list of as many primes as we want, using loopings, in C++.

Prime numbers in Math

A number is said to be prime when it can be divided only by 1 and by itself.
The 7 is prime, you can only divide by 1 and 7, by any other value will give a decimal result.

The 12 is not prime because it can be divided by 1, 2, 3, 4, 6 and 12.

Let's look at some prime numbers: 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83 , 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367 , 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521 , 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599, 601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677 , 683, 691, 701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857 , 859, 863, 877, 881, 883, 887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997 ...

Prime numbers ​​are a very special class in mathematics, having utility in many branches and areas, such as cryptography.

It is worth researching about them, there is a whole veil of mystery in them, as they have been trying for millennia to find a formula to generate prime numbers and nothing to date has worked.

Will you ever make it? Maybe ... if you win the Nobel Prize, don't forget to share the money with us ...

Do you wanna to hunt some prime numbers?

How to Find Out if a Number is Prime

To check if a num number is prime, just check its dividers, from 1 to num.
For example, let's test if 9 is prime. Just look at the rest of the division by 1, 2, 3, 4, 5, 6, 7, 8, and 9.

If it is prime, it will only be divisible by 1 and by itself, so it will have 2 dividers. But the rest of the division will give 0 when we do 9%3, so 3 is also divisor, totaling 3 dividers, so not prime.

Now the 11.
We can take the rest of the division by 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 and 11, which will only give 0 to 1 and to 11.

So he is prime.

That is, just do the rest of the division from num by 1, 2, 3, 4, 5, ..., up to num, and count in the div variable (initialized with 0) how many dividers there are.

If it's 2, it's prime.
If it's more than 2, it's not a prime.

See the code:

#include <iostream>
using namespace std;

int main()
{
    int aux, num=479001599, div=0;

    for(aux=1 ; aux<=num ; aux++)
        if(num%aux==0)
            div++;

    if(div==2)
        cout<<"Prime"<<endl;
    else
        cout<<"Not prime"<<endl;
    return 0;
}

We tested with a giant prime number, 479001599.
It took 1,831s here to check, and on your machine?

Optimizing the search for prime numbers

Now every number is divisible by 1.
So we don't have to do the rest of the division by 1, it's a check less.

And we don't have to test until num either.
It's over half, there won't be any more splits possible.

Dabbing at the code, it looks like this:

#include <iostream>
using namespace std;

int main()
{
    int aux, num=479001599, div=0;

    for(aux=2 ; aux<=num/2 ; aux++)
        if(num%aux==0)
            div++;

    if(div==0)
        cout<<"Prime number"<<endl;
    else
        cout<<"Not prime number"<<endl;
    return 0;
}

Now it only took 1,012s
And on your machine?

We can go further and calculate to the square root of num instead of just num/2 (search for this):

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int aux, num=479001599, div=0;

    for(aux=2 ; aux<=sqrt(num) ; aux++)
        if(num%aux==0)
            div++;

    if(div==0)
        cout<<"Prime"<<endl;
    else
        cout<<"Not prime"<<endl;
    return 0;
}

0.004s ! Wooooow!

Finding prime nubers in a range

Now let's print all primes in a certain range, from 1 to a Maximum value, like 100.
First, one variable to test all numbers from 2 to Max is aux.

For each number, we will count all the divisors and store in the div variable, so it must start at zero inside the first loop.

In the second FOR, we will check each aux number, doing the rest of their division by 2 to the square root of the number to see if there are any dividers.

If so, it falls into the IF (IF inside a FOR that's inside another FOR, how crazy!), Which increments div.

After all this internal checking, it is prime if div has 0 as its value, if so then we print the aux value as it is a prime.

Here's how the code looks:

#include <iostream>
#include <cmath>
using namespace std;

int main()
{
    int aux, coun, Max=100, div;

    for(aux=2 ; aux<=Max ; aux++){
        div=0;

        for(coun=2 ; coun<=sqrt(aux) ; coun++)
            if(aux%coun==0)
                div++;

        if(!div)
            cout<<aux<<" ";
    }

    cout<<endl;

    return 0;
}

Test with a thousand, ten thousands, a million ... just now you have a real sense of the power and calculating power of your machine

Fibonacci with C++ Loops

In this tutorial of our C++ course, we will learn how to display the terms of the Fibonacci series, using only loops!

Fibonacci in C++ with FOR

The first two terms in the series are: 0 and 1.
So let's order integers over 2.

Let's store in the last and second variables the last number of the sequence and the last one, initially:
ult = 1
penult = 0

We ask the number for the user and store it in n.
Let's go to our repetition structure, the FOR.

As we have already displayed the first two terms of the sequence: 0 and 1
Our counting starts at the third member of the sequence: aux = 3
And it even goes through n iterations: aux <= n
This ensures that no sequence elements are displayed.

Inside FOR, we first print the next term: ult + penult

Now comes the ace in the hole.
The new value of ult will be the sum of itself with the previous number, penult.
And the new value of penult will be ult.

We want to do this:
penult = ult = 1
ult = 1 + 0 = 1

The problem is that when we do: penult = ult, the original value of penult is lost, which is the old value we would use to calculate the new value of ult.

The solution to this is to store the old penult value in the temp temp variable.
Then just do:
temp = penult;
penult = ult;
ult = ult + temp;

There, now the sequence 'walked', and is ready to display the next term.

See how our code looks:

#include <iostream>
using namespace std;

int main()
{
    int n, aux, temp, ult=1, penult=0;

    cout << "Display how many terms: ";
    cin >> n;

    cout << penult << endl << ult << endl;

    for(aux=3 ; aux<=n ; aux++){
        cout << (ult+penult) << endl;

        temp = penult;
        penult = ult;
        ult = ult + temp;
    }

    return 0;
}

Fibonacci with WHILE in C++

#include <iostream>
using namespace std;

int main()
{
    int n, aux=3, temp, ult=1, penult=0;

    cout << "Display how many terms: ";
    cin >> n;

    cout << penult << endl << ult << endl;

    while(aux<=n){
        cout << (ult+penult) << endl;

        temp = penult;
        penult = ult;
        ult = ult + temp;

        aux++;
    }

    return 0;
}

Can you do with DO WHILE loop, which is calculating as many times as you want, in a loop that only ends when the user enters 0?

Write in the comments.

Summation and Factorial with C++ Loops

In this tutorial, we will solve two questions from our list of loop exercises, we will learn how to calculate the sum and factorial of a number, using only FOR or WHILE loops, in C++.

Summation with C++ loopings

The summation of a number n is nothing more than the sum of the numbers from 1 to n.

So first we ask the user for a positive integer and store it in variable n.
We will also use an aux auxiliary variable, which will traverse the values from 1 to n within the loop.

We will also use the sum variable, which will store the sum of all these numbers. Obviously, we must initialize it with value 0.

See how our code is using FOR loop:

#include <iostream>

using namespace std;

int main()
{
    int n, aux, sum=0;

    cout << "Summation: ";
    cin >> n;

    for(aux=1 ; aux<=n ; aux++)
        sum += aux;

    cout << "Summation: " << sum << endl;

    return 0;
}

Now with WHILE:

#include <iostream>

using namespace std;

int main()
{
    int n, aux=1, sum=0;

    cout << "Summation: ";
    cin >> n;

    while(aux<=n){
        sum += aux;
        aux++;
    }

    cout << "Summation: " << sum << endl;

    return 0;
}

With WHILE looping, can be calculated several times and typing 0 to end the loop:

#include <iostream>
using namespace std;

int main()
{
    int n, aux, sum;

    do{
        cout << "Summation: ";
        cin >> n;
        sum = 0;

        for(aux=1 ; aux<=n ; aux++)
            sum += aux;

        cout << "Summation: " << sum << endl;
        cout<<endl;
    }while(n);

    return 0;
}

Factorial using loops in C++

If the sum totals all numbers from 1 to n, the factorial multiplies all numbers from 1 to n.

The factorial symbol of a number is !.

For example:
4! = 1 x 2 x 3 x 4 = 24
5! = 1 x 2 x 3 x 4 x 5 = 120

Instead of sum let's use prod to store the product, and inicialize with 1.
And instead of adding (+=), let's multiply (*=).

Using FOR loop:

#include <iostream>

using namespace std;

int main()
{
    int n, aux, prod=1;

    cout << "Factorial: ";
    cin >> n;

    for(aux=1 ; aux<=n ; aux++)
        prod *= aux;

    cout << "Factorial: " << prod << endl;

    return 0;
}

WHILE:

#include <iostream>
using namespace std;

int main()
{
    int n, aux=1, prod=1;

    cout << "Factorial: ";
    cin >> n;

    while(aux<=n){
        prod *= aux;
        aux++;
    }

    cout << "Factorial: " << prod << endl;

    return 0;
}

DO WHILE:

#include <iostream>
using namespace std;

int main()
{
    int n, aux, prod;

    do{
        cout << "Factorial from: ";
        cin >> n;
        prod = 1;

        for(aux=1 ; aux<=n ; aux++)
            prod *= aux;

        cout << "Factorial: " << prod << endl;
        cout<<endl;
    }while(n);

    return 0;
}

Simple, right?

FOR Repetition Statement - C++ controlled loop

Concluding the presentation of the repetition structures of our C ++ Course, we will present the FOR statement, the controlled loop.

FOR repetition statement in C++

The FOR repetition statement has the following syntax:

for(inicialization ; conditional_test ; update){
   // codes that run if
   // the conditional test
   // is true
}

Come on.
The FOR repetition statement has three expressions within it, separated by semicolons.

The loop begins with some kind of initialization, usually a count variable, with some initial value.

After this initialization, conditional testing occurs. If true, the code inside the FOR loop braces is executed.
After each iteration, the 'update' occurs, where we usually update the counter value, most commonly it is a variable that will increment or decrement.

Then again the conditional test is performed, if true, again the FOR code is executed. After this iteration, the update occurs again.

FOR loop usage example

In programming, an example is worth a thousand words.
Let's count from 1 to 10, using the for loop, the code is as follows:

#include <iostream>
using namespace std;

int main()
{
    int count;

    for(count=1; count<=10 ; count++){
        cout << count << endl;
    }

    return 0;
}

Our control variable is count, which starts at 1.
Let's print it on screen as long as its value is less than or equal to 10.

At each iteration, we increment it by one (count++) because we want it to go from 1 to 10.

Note that we already did that in the WHILE loop, but we initialized the variables before the loop, inside that we updated the variable with each loop and the conditional test occurred inside the WHILE parentheses.

It occurs the same way in the FOR loop, but in a more organized way.

Using the FOR Repetition Statement

Let's do the opposite now, a countdown, which counts from 100 to 1.
For this, we initialize our control variable to 100.

The test to be performed is: count> 0
That is, as long as the variable has a value above 0, iterations of the FOR loop will occur.

And with each iteration we have to decrease the count, because it goes from 100 to 1, one by one.
See how our code looked:

#include <iostream>

using namespace std;

int main()
{
    int count;

    for(count=100; count>0 ; count--){
        cout << count << endl;
    }

    return 0;
}

Not always, however, we will increment or decrement by 1 in 1.
We can update our variables as we wish.

For example, let's print all even numbers from 1 to 1000 on the screen.
The first even is 2, so we initialize our variable with this value.

Let's increment by 2: count += 2

And the test is as long as the variable is less than or equal to one thousand: count <= 1000

#include <iostream>
using namespace std;

int main()
{
    int count;

    for(count=2; count<=1000 ; count+=2){
        cout << count << endl;
    }

    return 0;
} 

See the incredible speed with which this code executes.
Do you doubt the ability of C ++? Put 1 million.

When to use the FOR loop

Often we want to loop with a certain number of iterations.
For example, when asking for a student's grades, let's ask for as many grades as there are to average.

To calculate your income tax, we need to add up your entire salary of the year, ie 12 salaries.

The FOR loop is ideal when you know exactly the number of iterations you are going to do: "oh, I want to calculate this in this range from x to y", so bang, use the FOR repetition statement.

When you don't know when looping should end or have less control over how many iterations to occur, then use the WHILE loop.

Remembering that, deep down, they are absolutely the same thing.

It will only be easier to work with FOR sometimes and WHILE at other times.

FOR Repetition Statement

Create a program that asks how many grades you want to average, then asks each of those grades and finally displays the average.

Let's store the number of notes we will ask for in variable n.
The next step is to ask for grade by grade, and here comes the ace in the hole: calculate the sum of all grades.

Within the FOR, the control variable aux goes from grade 1 to the grade n, asking one by one and storing the grade in the variable grade.

Let's store in the sum variable, the sum of all these grades.
Finally, we display sum/n to display the average.

See our C ++ code:

#include <iostream>
using namespace std;

int main()
{
    int aux, n;
    float grade, sum=0;

    cout <<"How many topics: ";
    cin >> n;

    for(aux=1; aux<=n ; aux++){
        cout <<"Grade "<<aux<<": ";
        cin >> grade;
        sum += grade;
    }

    cout << "Average: "<<(sum/n)<<endl;

    return 0;
}

Notice how this repetition statement is controlled: it will always run 'n' iterations, whatever the value of 'n' (obviously, the number of grade must be a positive integer value).

You can fill in 2 grades, 3 grades, a thousand grades, a million grades ...
Powerful, isn't this FOR command?

DO ... WHILE C++ looping

In this C++ tutorial, we will learn how to use do ... while looping in C++, through ready-made examples with commented code.

DO ... WHILE Looping

To recap: loop is a certain piece of code that can be repeated as many times as we wish. We have already studied WHILE looping in C++, now let's know DO WHILE.

Remembering that in the WHILE loop, the conditional test occurs before the loop executes.

This is the main difference for the DO WHILE loop, in this, the conditional test will only happen after each iteration (loop internal code repetition).

The loop structure of WHILE is:

do
{
   // code
   // code
} while (condition) ; 

That is, the code is executed first (DO this).
Then the conditional test occurs within the parentheses of while.

If true, the code is repeated again and again as long as the condition is true.

See the flow chart:

How to use DO WHILE in C++

The first thing to keep in mind when deciding to use DO WHILE is that it will execute the code at least once! That is, always performs an iteration of the loop!

A very common use is in menus. A menu is always displayed at least once (either in a game or in your banking system).
Let's create a menu of a bank.

See our code:

#include <iostream>
using namespace std;

int main()
{
    int op;

    do
    {
        cout << "Choose an option:\n";
        cout << "0. Exit\n";
        cout << "1. Balance\n";
        cout << "2. Extract\n";
        cout << "3. Withdraw\n";
        cout << "4. Transfer\n";
        cin >> op;

    } while(op);

    return 0;
}

Each time you type an option, it can go to a different section of the system (we'll learn how to do that using functions), and only comes out if you type 0 (ie as long as the op value is different from 0, the loop occurs, because any value other than 0 is true, only 0 is False).

Note that we do not even need to initialize the variable (if we were to use the while loop, we would need to initialize, to ensure that the loop occurred at least once).

DO WHILE example usage

We use the while looping too when we want to do something at least once, and we want to give it the option of repeating itself again.

For example, the code below calculates the average of two grades the user provides.
At the end, he asks if you want to calculate another average:

#include <iostream>
using namespace std;

int main()
{
    float grade1, grade2;
    int op;

    do
    {
        cout << "First grade: ";
        cin >> grade1;

        cout << "Second grade: ";
        cin >> grade2;

        cout <<"Average: " << (grade1+grade2)/2 << endl;
        cout <<"Calculate again ?\n";
        cout <<"1. Yes\n";
        cout <<"2. No\n";
        cin >> op;

    } while(op!=2);

    return 0;
}

That is, the person using this program can calculate as many averages as he or she wants, infinitely, thanks to the do while looping.

So whenever you need to run code at least once (but you don't know how many times, it depends on the user), use DO WHILE looping.

For example:

do
{
   cout << "Blablabla (or type 0 to exit): ";
   //code
   //códe
} while(op);

Cool, isn't?

The WHILE Loop in C++: How to Use the Repetition Structure

In this looping tutorial, we will introduce the while repetition structure in C++.

WHILE Loop: Repetition Structure

As the name may suggest in the introduction, it is a structure that allows us to repeat certain pieces of code in C++.

The structure of C ++ is as follows:

while(test){
   // Statement in case of 
   // test expression be true
}

So it starts with the while statement, then parentheses, and within these must have some boolean value, usually an expression, a conditional test that will return true or false.

While that value within parentheses is true, the code inside the while statement will run.

Each repetition is called an iteration. There can be none, one, one thousand, one million or infinite iterations in a loop (infinite loopings), it will depend on how the conditional test behaves.

See the WHILE loop flowchart:

WHILE Example - Repetition Structure

Let's go to the examples, so we learn better.

Let's create a program that displays numbers from 1 to 10 on the screen.
For this, let's use a control variable, let's call count, because it will be our counter.

We start with value 1.
The conditional test is: as long as count is less than or equal to 10
Inside WHILE we give cout to print the number.

Then we have to increment the counter by one, see the code:

#include <iostream>
using namespace std;

int main()
{
    int count=1;

    while(count<=10){
        cout << count << endl;
        count++;
    }
    return 0;
}

What happens is as follows. The code arrives in WHILE, and there it tests if the variable is less than or equal to 10.

As it is worth 1, the test is true and enters the code. There we print the variable, and increment the counter.

Then the test occurs again, now our variable is worth 2 and gives true to the test, running its code.
Then the test occurs with the counter worth 3, and so on, until the counter is 10.

In this case, the test is still true.
But within the code, the counter increments and turns 11.

When retesting, the result is false, so the repeat structure stops the iterations and ends the loop.

Here's what the code would look like, displaying from 10 to 1:

#include <iostream>
using namespace std;

int main()
{
    int count=10;

    while(count>0){
        cout << count << endl;
        count--;
    }
    return 0;
}

How to use WHILE loop in C ++

The example below is infinite looping, but the test inside the WHILE loop is always true, so he would be printing the message endlessly ...

#include <iostream>
using namespace std;

int main()
{
    while(1)
        cout << "Progressive C++ course\n";

    return 0;
}

We can also do an infinite count:

#include <iostream>
using namespace std;

int main()
{
    int count=1;

    while(count++)
        cout << count << endl;

    return 0;
}

Note that we place the increment operator directly inside the while loop.
We also do not use braces, this is allowed as the while code has only one line.

WHILE in C ++: Validating Entries

One of the features of the WHILE command is to validate user input.
For example, let's ask the user for a grade from 0 to 10.

If it type less than 0 or greater than 10, it will enter WHILE.
Within the repeating structure, we warn him that he entered a wrong note and we ask him to insert the note again.

The while loop is a stubborn loop ... it repeats as many times as necessary.
Want to see? Test placing notes less than 0 or greater than 10, it will only stop when the entered note is between 0 and 10:

#include <iostream>
using namespace std;

int main()
{
    int grade;

    cout << "Type a grade: ";
    cin >> grade;

    while(grade<0 || grade>10){
        cout <<"Invalid grade, try again: ";
        cin >> grade;
    }

    return 0;
}

Very simple, but powerful, this control structure.

Example of using WHILE in C ++

Create a program that prompts the user for a number and displays the multiplication table of that number.
Let's store the number entered in variable num. Our control variable is aux, which will range from 1 to 10.

See how our code looks:

#include <iostream>
using namespace std;

int main()
{
    int num, aux=1;

    cout << "Type a number: ";
    cin >> num;

    while(aux<=10){
        cout <<num<<" x "<<aux<<" = "<<num*aux<<endl;
        aux++;
    }

    return 0;
}

Assignment, increment and decrement operators

Before we get into C++ loop studies, we need to know and learn how to use some operators that are important in studying repetition structures.

These operators will allow us to 'save' code, ie write less.
Obviously, we programmers are not lazy. We are just efficient, ok?

Assignment Operators

We have sometimes used expressions like:
x = x + 1;
This means "make variable x its old value plus 1".

However, this can be abbreviated to:
x += 1;
It means the same thing.

If we want to subtract y from x, we can do:
x = x - y;

Or more simply:
x -= y;

To make x receive the product value of x by y:
x = x * y;

Or in a lazier way:
x *= y;

The same goes for division and rest of division (module):
x /= y; is the same as x = x / y;
x %= y; is the same as x = x% y;

Very simple, no? Just one way to write less.

Increment and Decrement Operators

Do you think:
x + = 1;
x = 2;
Is it writing little?

There are two ways to do this for each expression:
x ++ or ++ x
x-- or --x

If we use these expressions alone:
x ++; and ++ x;
x--; and --x;

They will have the same effect: increment in the first case and decrement in the second case by one unit.

The variations: ++ x and x ++ are called preincrement and postincrement
The variations: --x and x-- are called pre-decrement and post-decrement.

They work as follows ... suppose the expression:
y = x++;

Two things happen in that order:

1. y gets the value of x
2. x is incremented by one unit

Already in the expression:
y = ++ x;

The following occurs:

1. x value is incremented by one unit
2. y gets new x value, incremented

See the following program. What prints on the screen?

#include <iostream>
using namespace std;

int main()
{
    int x=1;

    cout << x++;
    return 0;
}

The answer is 1. First print x, then increment x.
Put another cout for you to see the new x value later.

And the following program, which output will have?

#include <iostream>
using namespace std;

int main()
{
    int x=1;

    cout << ++x;
    return 0;
}

Now yes, directly prints 2.
First the increment (++) occurs, and only then the value of x is printed.

Now let's look at another sequence of operations:
x = 2;
y = 3;
z = x * ++y;

What are the values of x, y and z after these three procedures?
Come on.

First, y is incremented to 4.
So we have z = x * y = 2 * 4 = 8
The new values are 2, 4 and 8.

Now let's look at this sequence of operations:
x = 2;
y = 3;
z = x * y--;

The value of z is: z = x * y = 2 * 3 = 6

Since the decrement sign came after the variable y, only then is it decremented to become 2. The new values are 2, 2, and 6.