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

Progressive C++