Numbers and arithmetic · 3 of 4 Advanced
Primes and sieves
Test a number for primality and factor it by trial division up to the square root, and find every prime below a limit with a sieve.
Books1
Links3
- Divisibility Prime factorization with a worked table, then CSES Counting Divisors solved twice: by trial division, and by a sieve that stores a prime divisor of every number. usaco.guide (opens in a new tab)
- Sieve of Eratosthenes Derives the sieve’s running time, then speeds it up by sieving odd numbers only, using bits and processing the range in blocks. cp-algorithms.com (opens in a new tab)
- Legendre’s formula The general rule behind the trailing-zeros count: the exponent of any prime p in n! is the sum of \lfloor n / p^i \rfloor. en.wikipedia.org (opens in a new tab)
More links4
- Python Program for Sieve of Eratosthenesgeeksforgeeks.org (opens in a new tab)
- CP-Algorithms - Euler Totient Functioncp-algorithms.com (opens in a new tab)
- CF Blog — Sieve of Eratosthenes and Factorizationcodeforces.com (opens in a new tab)
- Errichto – Number Theory for CPyoutube.com (opens in a new tab)