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