Primality Testing and Finding Divisors

Definitions of primes, divisors, and multiples

A prime is called “prime” in English. If $p$ is prime, then $p^k$ is called a prime power.

For integers $a, b$, we say $a$ divides $b$ if there exists an integer $n$ such that $b = a n$. In this case $b$ is called a multiple of $a$.

A natural number $p \ge 2$ is a prime if its only divisors are $1$ and $p$.

Primality test

Start from the definition.
Test all divisors from $1$ to $N$. If exactly two numbers divide $N$, then $N$ is prime.

Equivalently, try dividing $N$ by each integer from $2$ to $N-1$. If any divides evenly, $N$ is composite; if none do, $N$ is prime.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int isPrime(int n) {
    if (n < 2) {
        return false;
    }
    for (int i = 2; i < n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

This c++ function checks whether a number is prime.
Since it starts from 2, you must handle the case when the input is 1.

The loop checks all numbers from $2$ to $N-1$, so the time complexity is $\bigo(N)$.

Optimizing the primality test

Let $d$ be the smallest divisor of a composite $N$ other than $1$.
Then $\frac{N}{d}$ is also a non-unit divisor of $N$, so $d \le \frac{N}{d}$.
Rearranging gives $d^2 \le N$, hence $d \le \sqrt{N}$.

So it suffices to test divisors only up to $\sqrt{N}$.

You could write the loop as (int i = 2; i <= sqrt(n); i++), but sqrt uses floating-point arithmetic and may introduce error. Prefer for (int i = 2; i*i <= n; i++).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
int isPrime(int n) {
    if (n < 2) {
        return false;
    }
    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0) {
            return false;
        }
    }
    return true;
}

The time complexity is $\bigo(\sqrt{N})$.

Practice problems for primality testing

Finding divisors

A small tweak lets us list divisors.

Iterate $i$ from $1$ to $\sqrt{n}$ and push each divisor into a vector.

If a natural number $d$ divides $n$, then $n/d$ is also a divisor.
Be careful when $n$ is a perfect square $m^2$: $\sqrt{n} = m$ would be counted twice unless you check.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> v;
    
    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            v.push_back(i);
            int d = n / i;
            if (i != d)
                v.push_back(d);
        }
    }
    
    sort(v.begin(), v.end());

    cout << "Divisors of " << n << ": ";
    for (int i : v) {
        cout << i << ' ';
    }
}

This lists all divisors in $\bigo(\sqrt{N})$ time.

After collecting divisors we sort them. The STL sort runs in $\bigo(N\log N)$.

You can roughly estimate the upper bound on the number of divisors within the long long range as about $\sqrt[3]{N}$.
So even in the worst case the sorting cost is at most $\bigo(\sqrt[3]{N}\log \sqrt[3]{N})$.

Since for positive $N$ we have $\sqrt[3]{N}\log \sqrt[3]{N} < \sqrt{N}$, the overall complexity remains $\bigo(\sqrt{N})$.

Optimizing divisor listing

We can avoid sorting.

Instead of v.push_back(d);, push $d$ into a temporary vector and then append that vector in reverse to get sorted divisors.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> divisor;
    vector<int> tmp;

    for (int i = 1; i * i <= n; i++) {
        if (n % i == 0) {
            divisor.push_back(i);
            int d = n / i;
            if (i != d)
                tmp.push_back(d);
        }
    }

    divisor.insert(divisor.end(), tmp.rbegin(), tmp.rend());

    cout << "Divisors of " << n << ": ";
    for (int i : divisor) {
        cout << i << ' ';
    }
}

Practice problems for divisors

Listing all primes in a range

Brute-force primality checks will time out for large ranges.
Use the Sieve of Eratosthenes.

For the algorithm and optimizations, see here. Code only below:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
vector<int> findPrime(int max) {
    vector<int> prime;
    vector<bool> check(max + 1, false);
    prime.push_back(2);
    for (int t = 3; t <= max; t += 2) {
        if (!check[t]) {
            prime.push_back(t);
            for (int i = t * t; i <= max; i += t) {
                check[i] = true;
            }
        }
    }
    return prime;
}

Prime factorization

With the above, prime factorization is straightforward.
factorize factors a given $N$ efficiently.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <vector>
#define ull unsigned long long
using namespace std;

vector<ull> factorize(ull n) {
    vector<ull> factors;
    for (int i = 2; i * i <= n; i++) {
        while (n % i == 0) {
            factors.push_back(i);
            n /= i;
        }
    }
    if (n > 1) {
        factors.push_back(n);
    }
    return factors;
}

int main() {
    ull n;
    cin >> n;
    vector<ull> factors = factorize(n);
    cout << "Prime factorization of " << n << ": ";
    for (int i = 0; i < factors.size(); i++) {
        cout << factors[i] << ' ';
    }
    if (factors.size() == 1) {
        cout << "(prime)";
    }
}

Bonus algorithms

Number theory includes many challenging but interesting algorithms. Not strictly necessary, but worth noting.

Pollard’s Rho factorization

The above factorization is fine for int, but for long long it can TLE.

For problems like this with $1 \le N \le 10^{18}$, implement Pollard’s Rho with Miller–Rabin primality testing, factor $N$, then enumerate divisors via DFS.

I may cover these algorithms later.

Prime counting function

The prime counting function $\pi(n)$ gives the number of primes $\le n$.
It satisfies the approximation

$$\pi(n) \approx \frac{n}{\ln(n)}.$$

For example, an approximation for $\pi(10^6)$ is $72382$, while the exact value is $78498$.

This function lets you estimate time complexity in problems involving the count of primes.