Number Theory Basics

The problem

Many problems ask about primes (numbers above 1 with no divisors except 1 and themselves), divisors, or the greatest common divisor (gcd, the largest number dividing both). Typical questions:

• Is $n$ prime? Which numbers up to $10^6$ are prime?
• What is the prime factorisation of $x$ (for example $360 = 2^3 \cdot 3^2 \cdot 5$)?
• List all divisors of $n$, or count them.
• What is $\gcd(a, b)$ and $\operatorname{lcm}(a, b)$ (least common multiple)?