[prev] [index] [next]

Performance Example (cont)

If we think more about the definition of primality ...
  • if there are divisors, at least one must be sqrt(n)
  • hence we can terminate the loop at sqrt(n)   ⇒ O(sqrt(n))
  • also, terminate as soon as we find any divisor 

int is_prime(int n)
{
    int i; assert(n > 2);
    for (i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return 0;
    }
    return 1;
}