Sieve of Eratosthenes

To find all primes through n, create isPrime initialized true for indices 2..n, then mark 0 and 1 false. For every p from 2 while p*p <= n, skip it if already marked composite. Otherwise mark p*p, p*p+p, ... as composite. Starting at p*p is essential: every smaller multiple p*k has k < p and was already marked when processing that smaller factor. At the end, every true index is prime. Use a multiplication-safe loop condition such as p <= n / p if integer overflow is possible. The sieve uses O(n) memory and O(n log log n) time, much better than testing every candidate by trial division when many primality answers are needed. If only one huge number is queried, trial division or Miller-Rabin may be a better fit.