Table of Contents

Introduction

Mathematicians have tried in vain to this day to discover some order in the sequence of prime numbers, and we have reason to believe that it is a mystery into which the human mind will never penetrate. — Leonhard Euler

Well that is indeed true. Primes numbers pose some of the notoriously hard problems in the field of Number Theory.

In this meet, we will mostly talk about prime numbers - how to find and use them - especially in the context of Competitive Programming.

So what are we going to cover in the meet?

1. How to find primes? (Sieve algorithms)

2. Totient Function

3. Integer Factorization algorithms

4. Primality Testing

5. ... and lots of problems on the above

How to find primes?

Problem: Given a number $n$ find all the primesm in the segment $[1:n]$.

So how do we proceed?

Well, the earliest known algorithm for this above task is the Sieve of Eratosthenes.

A simple yet massively insightful algorithm, it is still one of the most efficient ways to find all of the smaller primes.

Sieve of Eratosthenes

vi sieve(int n)
{
    int is_composite[n + 5] = {0};
    is_composite[0] = is_composite[1] = 1;

    for (int i = 2; i * i <= n; i++)
        if (!is_composite[i])
            for (int j = i * i; j <= n; j += i)
                    is_composite[j] = 1;

    vi primes;
    for (int i = 0; i <= n; i++)
        if (!is_composite[i])
            primes.push_back(i);
    return primes;
}

Complexity: $O(n \ln \ln n)$

But can this be made faster?

Counting $d(n)$ and $\sigma(n)$ of a number

Given. $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$we have:

int num[n + 1], sum[n + 1];

for (int i = 1; i <= n; i++)
	 for (int j = i; j <= n; j += i)
		  num[j]++, sum[j] += i;

Linear Sieve

Well there are indeed many ways to construct a sieve algorithm which uses linear time complexity i.e., $O(n)$ rather than something of the form $n \ln \ln \sqrt n + o(n)$.

std::vector <int> prime;
bool is_composite[MAXN];

void sieve (int n) 
{
		std::fill (is_composite, is_composite + n, false);
		for (int i = 2; i < n; i++) 
		{
				if (!is_composite[i]) prime.push_back (i);
				for (int j = 0; j < prime.size () && i * prime[j] < n; j++) 
				{
						is_composite[i * prime[j]] = true;
						if (i % prime[j] == 0) break;
				}
		}
}

Euler's Totient Function

$\phi(n) = \text{total co-primes with respect to}\ n \in [1:n]$

// O(n log log n)
int totient[n + 1];

for (int i = 1; i <= n; ++i) 
		totient[i] = i;

for (int i = 2; i <= n; ++i)
		if (totient[i] == i)
			  for (int j = i; j <= n; j += i)
					  totient[j] -= totient[j] / i;

// O(n)
std::vector <int> prime;
bool is_composite[MAXN];
int phi[MAXN];

void sieve (int n)
{
		std::fill (is_composite, is_composite + n, false);
		phi[1] = 1;
		for (int i = 2; i < n; ++i) 
		{
				if (!is_composite[i]) 
				{
						prime.push_back (i);
						phi[i] = i - 1;					
						//i is prime
				}
			
				for (int j = 0; j < prime.size () && i * prime[j] < n; ++j) 
				{
						is_composite[i * prime[j]] = true;
						if (i % prime[j] == 0) 
						{
								phi[i * prime[j]] = phi[i] * prime[j];	
								//prime[j] divides i
								break;
						} 
						else 
								phi[i * prime[j]] = phi[i] * phi[prime[j]];	
								//prime[j] doesn't divide
				}
		}
}

Sieve over a given range

Suppose, you need to find primes in the range $[L:R]$ where $R - L + 1 \approx 10^7$ and $R \approx 10^{12}$.

#include <bits/stdc++.h>
#define int long long int
using namespace std;

#define vi vector<int>

// basic sieve
vi sieve(int n)
{
    int is_composite[n + 5] = {0};
    is_composite[0] = is_composite[1] = 1;

    for (int i = 2; i * i <= n; i++)
        if (!is_composite[i])
            for (int j = i * i; j <= n; j += i)
                    is_composite[j] = 1;

    vi primes;
    for (int i = 0; i <= n; i++)
        if (!is_composite[i])
            primes.push_back(i);
    return primes;
}

// sieve in a range
void sieve_in_range(int l, int r)
{
    int sqrt_r = sqrt(r);
    vi primes_till_root_r = sieve(sqrt_r);

    vi is_prime(r - l + 1, true);
    if (l == 1) is_prime[l - 1] = false;

    for (int i: primes_till_root_r)
    {
        int x = (l / i) * i;
        if (x < l) x += i;

        for (int j = max(x, i * i); j <= r; j += i)
            is_prime[j - l] = false;
    }

    for (int i = 0; i < is_prime.size(); i++)
        if(is_prime[i])
            cout << (l + i) << endl;
}

signed main()
{
    // int n;
    // cin >> n;
    // sieve(n);
    
    int l, r;
    cin >> l >> r;

    cout << "Required primes in given range are:" << endl;
    sieve_in_range(l, r);

    return 0;
}

Integer Factorization

Problem: Find the factors of a given number.

// Type 1

factorization.push_back(1);

for (int d = 2; d <= n; d++)
{
		if (n % d == 0)
		   factorization.push_back(d);
}


// Type 2

factorization.push_back(1);

for (int d = 2; d <= (int)sqrt(n); d++)
{
		if (n % d == 0)
		{
		   factorization.push_back(d);
			 if (d != n / d)
					factorization.push_back(n / d);
		}
}

if (n > 1)
   factorization.push_back(n);

// Type 3

factorization.push_back(1);

for (int d = 2; d * d <= n; d++) 
{
     while (n % d == 0) 
		 {
        factorization.push_back(d);
        n /= d;
     }
}

if (n > 1)
   factorization.push_back(n);

// Type 4

factorization.push_back(1);

for (int d : primes) 
{
     if (d * d > n)
        break;
     while (n % d == 0) 
		 {
        factorization.push_back(d);
        n /= d;
     }
}

if (n > 1)
   factorization.push_back(n);

Primality Testing

Problem: Check whether a given number is prime.

bool is_prime(int n)
{
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0)
            return false;

    return true;
}

This algorithm has a time complexity of $O(\sqrt n)$.

Prime Number Theorem

Miller-Rabin Primality Test

A moderately fine explanation of the below algorithm is present in https://cp-algorithms.com/algebra/primality_tests.html.

using u64 = uint64_t;
using u128 = __uint128_t;

u64 binpower(u64 base, u64 e, u64 mod) 
{
    u64 result = 1;
    base %= mod;
    while (e) 
		{
        if (e & 1)
            result = (u128)result * base % mod;
        base = (u128)base * base % mod;
        e >>= 1;
    }
		return result;
}

bool check_composite(u64 n, u64 a, u64 d, int s) 
{
    u64 x = binpower(a, d, n);
    
		if (x == 1 || x == n - 1)
        return false;
	   
		for (int r = 1; r < s; r++) 
		{
        x = (u128)x * x % n;
        if (x == n - 1)
            return false;
    }
    
		return true;
}

bool MillerRabin(u64 n) 
{
    if (n < 2)
        return false;

    int r = 0;
    u64 d = n - 1;
    while ((d & 1) == 0) 
		{
        d >>= 1, r++;
    }
		
		int arr[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
    for (int a : arr)
		{
        if (n == a)
            return true;
        else if (check_composite(n, a, d, r))
            return false;
    }

    return true;
}

Guide to Complexity Analysis