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

Powerball Lottery with C++

In this C ++ tutorial, we will learn how to count all possible Powerball guesses, as well as how to display all these numbers using the nested repeating structures technique;

The Powerball lottery

Most likely you already played at the Powerball right?
It works like this: You must choose 5 numbers from a universe of 69 numbers, from 1 to 69 and one number of 26.


In the end, they display the result in ascending order of values, ie from the smallest to the largest.

The 'lowest' guess is:
1 2 3 4 5  - 1

Already the 'biggest' guess is:
65 66 67 68 69 - 26

Here comes the secret:

The first dozen goes from 1 to 65
The second dozen goes from 2 to 66
The third dozen goes from 3 to 67
The fourth dozen goes from 4 to 68
The fifth dozen goes from 5 to 69
The last goes from 1 to 26

How many guesses are possible in Powerball

So, come on.

Let's use 6 variables for the numbers: ten1, ten2, ten3, ten4, ten5, and ten6.

The accumulator variable, to count how many iterations (hence, how many guesses are possible in the Powerball), is the sum.

Now just make FOR nested with FOR and count how many possibilities there are, always being careful about the interval each dozen can take.

Another important secret is that the variable ten1 starts from 1, and the following starts from the previous decade plus 1, since the tens are larger than the others, since we are assuming they are in ascending order. The last one, don't.

The code:

#include <iostream>
using namespace std;

int main()
{
    int dez1, dez2, dez3, dez4,
        dez5, dez6, sum=0;

    for(dez1=1; dez1<=65 ; dez1++)
        for(dez2=dez1+1; dez2<=66 ; dez2++)
            for(dez3=dez2+1; dez3<=67 ; dez3++)
                for(dez4=dez3+1; dez4<=68 ; dez4++)
                    for(dez5=dez4+1; dez5<=69 ; dez5++)
                        for(dez6=1; dez6<=26 ; dez6++)
                            sum++;
    cout << "Total: "<<sum<<endl;

    return 0;
}

The result

It took 0.821s here to run over 292 million iterations, and then on your machine?

Display all guesses from Powerball

Let's print all possibles results:

#include <iostream>
using namespace std;

int main()
{
    int dez1, dez2, dez3, dez4,
        dez5, dez6;

    for(dez1=1; dez1<=65 ; dez1++)
        for(dez2=dez1+1; dez2<=66 ; dez2++)
            for(dez3=dez2+1; dez3<=67 ; dez3++)
                for(dez4=dez3+1; dez4<=68 ; dez4++)
                    for(dez5=dez4+1; dez5<=69 ; dez5++)
                        for(dez6=1; dez6<=26 ; dez6++)
                            cout<<dez1<<"-"<<dez2<<"-"<<dez3<<"-"
                                <<dez4<<"-"<<dez5<<"--"<<dez6<<endl;

    return 0;
}

Note that now is waaaay longer, and this is because the cout function is slower, it takes time to display things on your screen, if the machine was just doing the calculations, as in the previous example, would be much faster. But here we have to show the results of the iterations, so it takes longer.

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.