Простые числа — это увлекательные математические сущности, которые интриговали математиков на протяжении веков. В этой статье блога мы углубимся в концепцию простых чисел и рассмотрим различные методы определения того, является ли число простым или нет, с использованием языка программирования Swift. Мы предоставим примеры кода для каждого метода, что позволит вам понять и реализовать их в ваших собственных проектах. Давайте начнем!

Метод 1: наивный подход
Наивный подход предполагает проверку, делится ли число на любое число от 2 до квадратного корня. Если оно делится на какое-либо число, то оно не является простым. В противном случае оно простое.

func isPrimeNaive(_ number: Int) -> Bool {
    if number < 2 {
        return false
    }

    for i in 2..<Int(sqrt(Double(number))) + 1 {
        if number % i == 0 {
            return false
        }
    }

    return true
}

Метод 2: оптимизированное пробное деление
В оптимизированном методе пробного деления мы дополнительно оптимизируем цикл, проверяя делимость только на простые числа до квадратного корня из заданного числа.

func isPrimeOptimizedTrialDivision(_ number: Int) -> Bool {
    if number < 2 {
        return false
    }

    let primes = [2, 3, 5, 7, 11] // Predefined list of prime numbers

    for prime in primes {
        if prime * prime > number {
            break
        }
        if number % prime == 0 {
            return false
        }
    }

    return true
}

Метод 3: Решето Эратосфена
Решето Эратосфена — это древний алгоритм, который эффективно генерирует все простые числа до заданного предела. Мы можем изменить его, чтобы определить, является ли конкретное число простым.

func isPrimeSieveOfEratosthenes(_ number: Int) -> Bool {
    if number <= 1 {
        return false
    }

    var sieve = [Bool](repeating: true, count: number + 1)
    sieve[0] = false
    sieve[1] = false

    var p = 2
    while p * p <= number {
        if sieve[p] {
            for i in stride(from: p * p, through: number, by: p) {
                sieve[i] = false
            }
        }
        p += 1
    }

    return sieve[number]
}

Метод 4: Малая теорема Ферма
Малая теорема Ферма гласит, что если p— простое число, то для любого целого числа a, a^(p-1) % pбудет равно 1. Этот подход обеспечивает вероятностную проверку простоты.

func isPrimeFermat(_ number: Int) -> Bool {
    if number <= 1 {
        return false
    }

    func power(_ base: Int, _ exponent: Int, _ modulus: Int) -> Int {
        if exponent == 0 {
            return 1
        }
        var result = power(base, exponent / 2, modulus)
        result = (result * result) % modulus
        if exponent % 2 == 1 {
            result = (result * base) % modulus
        }
        return result
    }

    let iterations = 5 // Number of iterations for accuracy

    for _ in 0..<iterations {
        let a = Int.random(in: 2..<number)
        if power(a, number - 1, number) != 1 {
            return false
        }
    }

    return true
}

В этой статье мы рассмотрели несколько методов определения того, является ли число простым или нет, с помощью программирования на Swift. Мы рассмотрели наивный подход, оптимизированное пробное деление, решето Эратосфена и малую теорему Ферма. Каждый метод имеет свои преимущества и может использоваться в зависимости от требований вашего проекта. Поняв и внедрив эти методы, вы сможете эффективно работать с простыми числами в своих программах на Swift.