BinaryInteger.isPrime

binary_integer_is_prime.swift

import Algorithms // @ https://github.com/apple/swift-algorithms/pull/46, to pull in `Sequence.reductions`.

extension BinaryInteger {
	func isPrime() -> Bool {
		switch self {
		case ..<0: return (-1 * self).isPrime() // Normalize sign.
		case 0, 1: return false
		case 2, 3: return true
		default: break
		}

		guard ![2, 3].contains(where: { isMultiple(of: $0) }) else { return false } // Bail out if `self`
		// is a multiple of two or three.

		// All primes must be in the form 6k ± 1 (note, this doesn’t imply that all
		// numbers in that form are prime) — so, we search for divisors matching this form
		// since, by the fundamental theorem of arithmetic, every positive integer is either prime or
		// the product of primes. `divisors` starts at `6*1 - 1 = 5` and then, using the cycling `[Self(2), 4]`,
		// we step to `6*1 + 1 = 7`, `6*2 - 1 = 11`, and so on and so forth.
		let divisors = [Self(2), 4].lazy
			.cycled() // Repeats the collection’s elements ad infinitum (also from the Algorithms package).
			.reductions(6 * 1 - 1, +) // The `Sequence` analog to
			// [`Publisher.scan`](https://developer.apple.com/documentation/combine/publisher/scan(_:_:)).

		return !divisors
			.prefix { $0 * $0 <= self } // We only need to check divisors less than the square root of `self`.
			.contains { isMultiple(of: $0) }
	}
}