Let’s suppose you change telephone number. Almost surely the first thing you think is “is my new phone number prime?”.
Since the number is small the naive method “let’s try to divide the phone number by all numbers less than it” is good (at least if you do it with the computer).
You can improve this method dividing you number only by prime numbers less than the number itself, since by Euler’s fundamental theorem of arithmetic we know that every number has a unique representation in prime factors.
Still better: if n has a prime factor p ≥ √n then n has also a prime factor less than √n, so it is sufficient to try only prime numbers less than √n to completely factor n.
Ok, so let’s do it! But how can we find prime numbers less than √n?
There is an interesting algorithm to find all numbers less then n in few time, the Sieve of Eratosthenes. You take a table with numbers from 1 to n, you highlight 2 and them make an X over the multiples of 2. The first remaining number is 3, so you highlight 3 and mark all multiples of 3. You repeat this elimination process until √n and in the table will survive only primes numbers less then n.
This algorithm is fast, in fact it requires O(n log log n) operations (in average log log n for each element computed), so in our case only requires O(√n log log n) (ok I’m cheating, our problem size is x = log n, so we are taking O(2x/2 logx) time only for computing the primes, so practically the same time we’ll spend in divisions).
By the Prime Number Theorem of Gauss we expect to find π(N) ~ N/log(N) primes less than N, so for N=√n in the worst case we’ll have to perform √n/log(n) trial divisions (each with a complexity log n log log n).
Ok, so let’s check if the phone number is prime! You can code your trial division program or find a working Java program here: https://github.com/zagonico86/my-snippets/blob/main/primes/EratostheneSieve.java
You can find better algorithms in Pollard’s Rho post and Quadratic Sieve post.
