Prime Numbers — Mysterious and Beguiling

All prime numbers except 2 are odd, this makes 2 the oddest prime.

There are 78498 prime numbers smaller than equal to 10⁶

This article is divided in two parts

1. Identifying whether a number is prime or not
2. Identifying all prime numbers smaller than 10⁶

How to Identify whether a number N is prime.

This is easy if any number from 2 to N-1 can divide N then N is not prime.

#include<iostream>
using namespace std;
int main() {
    int N = 78;
    bool prime = true;
    for(int i=2;i<N;i++) {
        if(N%i == 0) {
            prime = false;
            break;
        }
    }
    if(prime) {
        cout<<N<<" is prime";
    } else {
        cout<<N<<" is not prime";
    }
    return 0;
}
Output:
78 is not prime
Time Complexity : O(N)

Can we improve the complexity?

Yes. Lets see how.

Assume N = 30, lets break this into 2 multiples

2 x 15 = 30
3 x 10 = 30
5 x  6 = 30
6 x 5 = 30
10 x 3 = 30
15 x 2 = 30

If you observe carefully and try with other numbers as well, you will find that these multiples can be exactly divided in half, the 1st half is mirror of 2nd half. We do not need to check for multiples that we have already checked.

We only need to check till √N (because at √N the 1st and 2nd multiple are supposed to be equal)

#include<iostream>
#include<math.h>
using namespace std;
int main() {
    int N = 78;
    bool prime = true;
    for(int i=2;i<=sqrt(N);i++) {  // Observe <= sqrt(N)
        if(N%i == 0) {
            prime = false;
            break;
        }
    }
    if(prime) {
        cout<<N<<" is prime";
    } else {
        cout<<N<<" is not prime";
    }
    return 0;
}
Output:
78 is not prime
Time Complexity : O(√N)
This may not seem much, but we just reduced number of operations from 10^6 to 10^3

Find all prime number smaller than 10⁶

If we use the above two approaches, to check each number if it is prime.

Approach 1:
#include<iostream>
#include<math.h>
using namespace std;
int main() {
    bool prime[1000000];
    int N, count;
    for(N=2;N<1000000;N++) {
        bool isprime = true;
        for(int i=2;i<N;i++) {
            if(N%i == 0) {
                isprime = false;
                break;
            }
        }
        prime[N] = isprime;
        if(isprime) count++;
    }
    cout <<count<<endl;
}
Output: 78498
Complexity : O(N²)
Time Taken: 2 min 48 s 

Optimised Code:

Approach 2:
#include<iostream>
#include<math.h>
using namespace std;
int main() {
    bool prime[1000000];
    int N, count;
    for(N=2;N<1000000;N++) {
        bool isprime = true;
        for(int i=2;i<=sqrt(N);i++) {
            if(N%i == 0) {
                isprime = false;
                break;
            }
        }
        prime[N] = isprime;
        if(isprime) count++;
    }
    cout <<count<<endl;
}
Output: 78498
Complexity : O(N√N)
Time Taken: 0.38s

from 2min 48s →0.38s (under a second), this is why optimisation and knowledge of complexity is important.

Can we improve further?

Yes, Do you know about Sieve of Eratosthenes. Lets Discuss it.

Instead of checking for each number, we remove multiples from the list.

In the process if we encounter a number which is not a multiple of any smaller number then it is a prime, and we remove all multiples of that prime number.

#include<iostream>
#include<cstring>
using namespace std;
int main() {
    int count = 0;
    bool prime[1000000];
    memset(prime, true, sizeof(prime)); // marking all as true
    for(int i=2;i<=1000000;i++){
        if(prime[i]==true) { // if not false yet, then it is prime
            for(int j=2;j*i<=1000000;j++) {
                prime[i*j]=false; // marking multiples of i as false
            }
            count++;
        }
    }
    cout<<count<<endl;
}
Output: 78498
Complexity: O(N log log N)
Time Taken: 0.024s

Understanding the complexity:

N for outer loop
N/2 for multiples of 2
N/3 for multiples of 3
N/5 for multiples of 5
….

Y = N + N/2 + N/3 + N/4 + N/5 + N/6 + N/7 +N/8 +N/9 +N/10 + …
Y = N (1 + 1/2 + 1/3 + 1/4 + 1/5 +….
Y = N log N

but in actual equation all terms are not included like N/4, N/6, N/8, N/9

When computed and analysed mathematically it is upper bounded by N log log N. If interested you can follow these links here and here to read more in detail.

Complexity : O(N²) →O(N√N) →O(N log log N)
Time : 2min 48s → 0.38s →0.02s

Sieve and primes are widely used in competitive programming and are very important to understand well.

Related Topic : Segmented Sieve (used to find primes of even higher ranges)