Prime Numbers I

“Prime numbers are what is left when you have taken all the patterns away.” - Mark Haddon

A prime number is a whole number greater than 1 that is only divisible by 1 and itself. It is one of the most interesting and enigmatic class of numbers. Mathematicians have been trying to find patterns in prime numbers for thousands of years. Still, they remain a critical field of study and many open problems in mathematics involve primes. For example: the Goldbach’s conjecture, Wall-Sun-Sun Primes, Twin Prime conjecture, etc. Of course, the ultimate question also remains: are there any patterns in the distribution of prime numbers? We don’t know, but that hasn’t stopped us from using primes for various needs.

Particularly, in computer science, prime numbers are used for cryptography and security, error-correction codes, hash tables and many other things. In competitive programming, many question from number theory require knowldge of prime numbers to solve them. Let’s see how we can use them.

Finding Prime Numbers (Sieve of Eratosthenes)

Since we don’t know of any rules for the distribution of primes, we need to run a sort of simulation to identify prime numbers. One such efficient algorithm comes from the greek mathematician Eratosthenes.

The Algorithm

We go through numbers one by one and mark them if they are not prime (composite). How do we do that? If we have a number and it is not marked, then it is a prime number! Then, we mark all of its multiples as composite. Then we process the next number and so on.

Here is how the code looks,

vector<int> prime;

void sieve(int limit) {

    // create an array for marking numbers
    vector<bool> mark(limit + 1);

    // to identify all primes until the limit,
    // we only need to mark primes until sqrt(limit)
    // the rest of the primes will not have any unmarked
    // multiples inside the given limit (think about why that is :] )
    for (int p = 2; p*p <= limit; p++) {
        // if number is composite
        if (mark[p])
            continue;
        
        // it is a prime
        // mark all its multiples
        // all primes until (p*p) will have been marked by previous primes
        for (int i = p*p; i <= limit; i+=p) {
            mark[i] = true;
        }
    }

    // add all the primes to the prime vector
    for (int p = 2; p <= limit; ++p)
        if (!mark[p])
            prime.push_back(p);
}

Nice! We have now have access to prime numbers until a certain limit. This will work well for limits up to 10^7.

The time complexity of this code is (n log log n). Take note of this pattern. It looks like it should be n^2, but it is actually faster. This is a feature of the Harmonic Series and many problems require the use of nested loops that follow this pattern.

Application

Fundamental Theorem of Arithmetic: Every number greater than 1 can be represented uniquely as a product of primes.

More specifically we represent any number N as,

N = p1 ^ (a1) * p2 ^ (a2) * … * pn ^ (an)

This is one of the most important ideas in number theory and a very important tool for analyzing numbers. A lot of problems will require you to break numbers down into their prime factors.

Prime Factorization

We start from the smallest prime number and try to divide the number until it is no longer divisible by that prime. If, the relevant multiples of the prime exceeds the number, then we break out of the loop. If, after this whole process the number is greater than 1, then it is a prime number itself.

map<long long, int> factors;

for (int p : prime) {
    // check if all relevant factors have been factored out
    // use 1LL to avoid overflow errors
    if (1LL * p * p > N)
        break;

    // initialize exponent
    int e = 0;

    // divide until not divisible
    while (N % p == 0) {
        e++;
        N/=p;
    }

    // p is in N's factors
    if (e) {
        factors[p] = e;
    }
}

// check if the number itself still remains a prime
if (N > 1) {
    map[N] = 1;
}

If the sieve was run for numbers up to N, then we can safely factorize numbers up to N^2.

For numbers equal to or less than the limit, we can compute it even more elegantly by storing least prime factors for each number.

Counting Number of Divisors

From a number’s prime factorization, we can count the number of divisors it has using the concept of combinations.

Say the number is N = (p1 ^ a1) * (p2 ^ a2)

Here, to construct a divisor of N, we can select subsets of all the available primes (in N’s factorization). So the total number of divisors is,

NOD(N) = (a1 + 1) * (a2 + 1)

Here, a one is added to account for the fact that we can choose exponent 0 for the corresponding prime factor.

Counting Sum of Divisors

Sum of divisors can be counted in a similar way.

If N = (p1 ^ a1),

SOD(N) = 1 + p1 + (p1 ^ 2) + … + (p1 ^ a1) = ((p1 ^ (a1 + 1) - 1) / (p1 - 1))

Upon generalizing, SOD(N) = ((p1 ^ (a1 + 1) - 1) / (p1 - 1)) * ((p2 ^ (a2 + 1) - 1) / (p2 - 1)) * …

Practice Problems

Remember the most critical analysis tool we have learned here to solve these problems. Good luck! :)