1/*
2 * Copyright 2020, Data61, CSIRO (ABN 41 687 119 230)
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#define SQRT_UINT_MAX 65536
8
9/*
10 * Determine if the given number 'n' is prime.
11 *
12 * We return 0 if 'n' is composite, or non-zero if 'n' is prime.
13 */
14unsigned is_prime_linear(unsigned n)
15{
16    /* Numbers less than 2 are not prime. */
17    if (n < 2) {
18        return 0;
19    }
20
21    /* Find the first non-trivial factor of 'n'. */
22    for (unsigned i = 2; i < n; i++) {
23        if (n % i == 0) {
24            return 0;
25        }
26    }
27
28    /* No factors. */
29    return 1;
30}
31
32/*
33 * Determine if the given number 'n' is prime.
34 *
35 * We return 0 if 'n' is composite, or non-zero if 'n' is prime.
36 *
37 * Faster version that 'is_prime'; runs in O(sqrt(n)).
38 */
39unsigned int is_prime(unsigned int n)
40{
41    /* Numbers less than 2 are not primes. */
42    if (n < 2) {
43        return 0;
44    }
45
46    /* Find the first non-trivial factor of 'n' or sqrt(UINT_MAX), whichever
47     * comes first. */
48    /* Find the first non-trivial factor of 'n' less than sqrt(n). */
49    for (unsigned i = 2; i < SQRT_UINT_MAX && i * i <= n; i++) {
50        if (n % i == 0) {
51            return 0;
52        }
53    }
54
55    /* No factors. */
56    return 1;
57}
58
59