Numbers

In this doc we will talk about some interesting facts about numbers and how to deal with them in programming.

Basic Concepts

Prime Numbers

Prime numbers are numbers that are greater than 1 and have no divisors other than 1 and themselves. They are the building blocks of all other numbers and have many interesting properties.

质数是大于1且除了1和自身外没有其他因子的数。

How to check if a number is prime (ignore brute force method):

Method 1: Check divisibility up to the square root of the number.

1
2
3
4
5
6
7
8
9
10
11
12

extension Int {
    var isPrime: Bool {
        guard self >= 4 else { return self > 1 }
        var max = Int(Double(self).squareRoot())
        if max % 2 == 0 { max += 1 }
        for i in stride(from: 3, through: max, by: 2) {
            if self % i == 0 { return false }
        }
        return true
    }
}

More efficient method: Magic numbers 6k ± 1.

By observing the pattern of prime numbers, we can see that all prime numbers greater than 3 can be written in the form of 6k ± 1, where k is a positive integer.
So we can check the divisibility of the number by 6k ± 1 up to the square root of the number.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
extension Int {
    var isPrime: Bool {
        // <= 4, only 2 and 3 are prime
        guard self >= 4 else { return self > 1 }
        // This is to check if the number is divisible by 2 or 3. Needed prior to the loop because the loop starts from 5.
        if self % 2 == 0 || self % 3 == 0 { return false }
        // Pick the ceiling to make sure the loop tests in all possible ranges. For example, if the int is 17, if we don't pick the ceiling, `max` will be 4, and the loop will only test 5, which is not correct.
        let max = Int(ceil(Double(self).squareRoot()))
        for i in stride(from: 5, through: max, by: 6) {
            // % i is to check 6k - 1, % (i + 2) is to check 6k + 1
            if self % i == 0 || self % (i + 2) == 0 { return false }
        }
        return true
    }
}

当我们要进行整数的除法检查时，需要将这个小数向上取整，以确保不遗漏任何可能的整数因数。如果直接转换为 Int，则会向下取整，可能会漏掉一个关键因数。
例如，n = 17：

  • sqrt(17) 大约是 4.123，如果不取整，直接转换为 Int 得到的结果是 4。
  • 然而，4 是不足够进行完整检查的，因为你实际上需要检查 5，以确保没有因数遗漏。

Common Swift Methods Used to Deal with Numbers

1. abs

abs returns the absolute value of a number.

1
2
3
let a = -5
let b = abs(a)
print(b) // 5

2. min and max

min and max return the minimum and maximum of two numbers.

1
2
3
let a = 5, b = 10
let minNum = min(a, b), maxNum = max(a, b)
print(minNum, maxNum) // 5 10

3. round, ceil, and floor

round rounds a number to the nearest integer, ceil rounds up, and floor rounds down. They all return a Double value.
If you want to round a Double to an Int, you can use Int().

1
2
3
4
let a = 5.6
let roundNum = round(a), ceilNum = ceil(a), floorNum = floor(a)
print(roundNum, ceilNum, floorNum) // 6.0 6.0 5.0
print(Int(roundNum), Int(ceilNum), Int(floorNum)) // 6 6 5

4. isMultiple

isMultiple checks if a number is a multiple of another number.
This is same as number % anotherNumber == 0.

1
2
3
4
5
6
let a = 10, b = 5
let isMultiple = a.isMultiple(of: b)
print(isMultiple) // true because 10 is a multiple of 5 (10 = 5 * 2)
// or
let isMultiple = a % b == 0
print(isMultiple) // true

5. squareRoot

squareRoot returns the square root of a number.

1
2
3
let a = 25
let b = a.squareRoot()
print(b) // 5.0

This is the same as sqrt(Double(a)).

Both sqrt and squareRoot return a Double value and the efficiency is almost the same. Choose one based on code style.