Prime Numbers

Integer factorization is the process of decomposing a composite number into a product of smaller integers, if these integers are restricted to be prime numbers then the process is called prime factorization.

This article covers factorization using trial division and fermat factorization through Pollard's Rho algorithm and using the sieve of eratosthenes.

The divisor function returns the number of divisors of an integer. This article covers important relations of the divisor function and prime numbers.

A prime number is a natural number greater than $1$ which has no positive divisors other than $1$ and itself.

This article covers different algorithms for checking if a number is prime or not including a naive test, the erathostenes sieve, the euler primality test and the miller-rabin primality test.

This article describes and implements a solution for the following problem, given two numbers $n$ and $k$ find the greatest power of $k$

Let $n!_{\%p}$ be a special factorial where $n!$ is divided by the maximum exponent of $p$ that divides $n!$. This article describes this problem and its solution with an implementation in C++.

The erathostenes sieve is an algorithm to find prime numbers up to a positive number $n$ using $O(n)$ space.

Euler’s phi function represented as $\phi(n)$ gives for a number $n$ the number of coprimes in the range $[1..n]$, in other words the quantity numbers in the range $[1..n]$ whose greatest common divisor with $n$ is the unity. In this article I try to explain how it works and implement it in C++.