1114402Sru#include <math.h>
2114402Sru
3114402Sruint is_prime(unsigned n)
4114402Sru{
5114402Sru  if (n <= 3)
6114402Sru    return 1;
7114402Sru  if (!(n & 1))
8114402Sru    return 0;
9114402Sru  if (n % 3 == 0)
10114402Sru    return 0;
11114402Sru  unsigned lim = unsigned(sqrt((double)n));
12114402Sru  unsigned d = 5;
13114402Sru  for (;;) {
14114402Sru    if (d > lim)
15114402Sru      break;
16114402Sru    if (n % d == 0)
17114402Sru      return 0;
18114402Sru    d += 2;
19114402Sru    if (d > lim)
20114402Sru      break;
21114402Sru    if (n % d == 0)
22114402Sru      return 0;
23114402Sru    d += 4;
24114402Sru  }
25114402Sru  return 1;
26114402Sru}
27