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