Surely that is the Sieve of Eratosthenes.
No, for 100 you would
test up to √100 using 2, 3, 4, 5, 6, 7, 8, 9, 10.
It says in
the Curious Incident of the Dog in the Night‑Time that the number of prime numbers up to a certain number
n is approximately proportional to log
n. If you already have a source of prime numbers in order, then you would need to check up to
ilog(√
n) numbers (
i being an unspecified integer). But log(√
n) = ½log(
n), so that reduces to logarithmic complexity.
In Abelson and Sussman it mentions a simpler method of finding whether a number is prime which runs in constant time but may miss out some values. So,
1: Populating a sieve runs in nlogn time.2: Using a ready‑made sieve to find whether a number is prime runs in logarithmic time.3: Testing for primeness without a sieve runs in √n time at worst. Somebody may be able to show it is quicker. Since most factors are small (2, 3, 5 etc) it may actually run in logarithmic time. Not sure, however.