Prime numbers

Prime numbers are numbers that can only be divided by itself and one. A prime number has two divisors so one is not a prime number. Prime numbers have been proved that there are a infinity of them by Euclid in Euclid's Element. Two numbers are said to be coprime if the only divisor that divides both of them is one (gcd(a,b) = 1). Here, we are going to tell you different ways to check if a number is a prime number. One technique is to do a brute force algorithm, this algorithm will see if there is a number from 2 to n-1 that can divide n.

Brute force

Pseudo-code :

for i=2 to i=n-1 i += 1 {
    if n % i == 0 {
        print : n is composite
        break
    }
}

C++ code :

for (int i=2; i<=n-1; ++i){
    if (n%i == 0){
        cout << n " is composite\n";
        break;
    }
}

Optimisation : you might have already seen that n can not be divided by sqrt(n)+1 so in the above for loop you could replace n-1 and put sqrt(n). This algorithm can be inefficient if we have two thousand integers to check.

Sieve of Eratosthenes

This solution consists to take the next  number let's say n that has not been marked as true and every number that have n as divisor and have not been marked are marked as true.

Pseudo-code for finding prime numbers from 2 to 100000 :

for i=2 to i=100000 i += 1 {
    if not vu[i] {
        for j=2*i to j=100000 j += i vu[j]=true;
    }
}
// all numbers where vu[i] = false are prime numbers

C++ code for finding prime numbers from 2 to 100000 :

for (int i=2; i<100001; ++i){
    if (!vu[i]){
        for (int j=2*i; j<100001; ++j) vu[j]=true;
    }
}
// all numbers where vu[i] = false are prime numbers

Optimisation : In the first loop, we can see that we only need to do the loop to sqrt(100000) or sqrt(n). In this case n=100000. Also it is possible to do this algorithm in O(n).