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