1*89a07cf8Schristos /* $NetBSD: prime.cpp,v 1.1.1.1 2016/01/13 18:41:48 christos Exp $ */ 2*89a07cf8Schristos 3*89a07cf8Schristos #include <math.h> 4*89a07cf8Schristos is_prime(unsigned n)5*89a07cf8Schristosint is_prime(unsigned n) 6*89a07cf8Schristos { 7*89a07cf8Schristos if (n <= 3) 8*89a07cf8Schristos return 1; 9*89a07cf8Schristos if (!(n & 1)) 10*89a07cf8Schristos return 0; 11*89a07cf8Schristos if (n % 3 == 0) 12*89a07cf8Schristos return 0; 13*89a07cf8Schristos unsigned lim = unsigned(sqrt((double)n)); 14*89a07cf8Schristos unsigned d = 5; 15*89a07cf8Schristos for (;;) { 16*89a07cf8Schristos if (d > lim) 17*89a07cf8Schristos break; 18*89a07cf8Schristos if (n % d == 0) 19*89a07cf8Schristos return 0; 20*89a07cf8Schristos d += 2; 21*89a07cf8Schristos if (d > lim) 22*89a07cf8Schristos break; 23*89a07cf8Schristos if (n % d == 0) 24*89a07cf8Schristos return 0; 25*89a07cf8Schristos d += 4; 26*89a07cf8Schristos } 27*89a07cf8Schristos return 1; 28*89a07cf8Schristos } 29