Computing Prime numbers faster with C++

Introduction

“Prime numbers are numbers which are divisible by 1 and itself” by definition. So why do we need to know about prime numbers? How do we find them using a computer program? How do we generate them? If generated, is there a faster method? This post answers these questions.

Application of Prime Numbers

Prime numbers have a wide range of applications in cryptography and pseudo random number generators. In cryptography, prime numbers are used to generate keys for public key techniques. The rand() function in C++ is also based on prime number generation. Let us create the best algorithm to generate prime numbers from scratch, analyze and improvise them.

Use of Modulo Operation

The modulo operator % gives the remainder when two numbers are divided:

2 % 2 = 0 // No remainder
5 % 4 = 1 // Remainder is 1

2 is divisible by 2 hence there is no remainder, but when 5 is divided by 4 the remainder is 1.

Let’s Code It!

The definition says “numbers which are divisible by 1 and itself.” So when a number is given, we check by dividing all numbers from 1 up to the given number. If we find that it has only 2 divisors, then it is prime.

On a computer, we count the number of modulo operations that result in zero:

The above gives us an idea of finding a pattern. See the zero counts of prime numbers and non-prime numbers. For example, 4 has 3 zeros as a result of modulo operation.

The left operand is constant (our variable n) and the right operand increments by one (variable i), so we use a loop. A counter variable increments when the modulus equals zero:

#include <iostream>
using namespace std;
int main(){
    int count=0;
    for (int i=1;i<=5;i++){
        cout << 5 << "%" << i << "= " << 5%i << endl;
        if (5%i==0){
            count++;
        }
    }
    if (count==2){
        cout << "Prime" << endl;
    }else{
        cout << "Not Prime" << endl;
    }
    system("pause");
    return 0;
}

Now the algorithm is made interactive by getting user input and checking whether it is prime.

Optimization: Checking up to n/2

As a programmer, we should improve the algorithm to take fewer steps. Basic algebra shows that it is enough to check from 1 to half of the number. Since 4×2 = 8, no factors will be greater than n/2. This saves computation time.

Here is a program demonstrating the performance difference when generating primes from 1 to 100 using both approaches (1 to n/2 vs. 1 to n):

The n/2 version requires significantly fewer operations than the traditional approach. This optimization becomes more impactful as the numbers get larger.