Primality test using a sieve (Prime Adventure part 5)
Channel: Art of the Problem
Date: 2012-10-21

An attempt at an optimal trial division primality test using the Sieve of Eratosthenes. We visualize the time complexity of storing all primes up to square root of n and then testing each one. Finally we ask: why can't we just store a precomputed list of primes in memory?