Check Prime Number

Q: Какова временная сложность проверки того, является ли число простым?

Пробное деление до √n занимает O(√n) времени и O(1) памяти. Для n до 2^31-1 это максимум около 46,000 делений или 23,000 , если пропустить чётные делители. Проверка каждого делителя до n-1 имеет сложность O(n) — около двух миллиардов шагов для наибольшего входного значения.

Q: Почему вы проверяете делители только до квадратного корня из n?

Делители образуют пары d и n / d , произведение которых равно n . Если бы оба были больше √n , их произведение было бы больше n . Значит, в каждой паре есть элемент не больше √n , и если до этого момента не обнаружится делитель, то n — простое число.

Q: Является ли 1 простым числом?

Нет. У простого числа ровно два различных делителя: 1 и оно само, а у 1 только один. Если пропустить 1 , разложение каждого целого числа на простые множители будет единственным. Вот почему isPrime(1) возвращает false .

НовичокМатематика и моделирование

+10

Простое число — это целое число больше 1, единственными делителями которого являются 1 и оно само. Вам дано положительное целое число n. Верните true, если n — простое число, и false в противном случае. Число 1 не является простым.

Функция

isPrime(n: integer) → boolean

ninteger: положительное целое число для проверки
Возвращаетboolean: true, если n — простое число, иначе false

Ограничения

1 ≤ n ≤ 2³¹ - 1

Примеры

Ввод: n = 29
Вывод: true
Пояснение: Ни одно из чисел 2, 3, 4 или 5 не делит 29, а 6 × 6 = 36 уже больше 29, поэтому больше не осталось делителей, которые нужно найти. 29 — простое число.

Ввод: n = 1
Вывод: false
Пояснение: Простое число имеет ровно два делителя: 1 и само себя. У 1 только один делитель, поэтому ответ — false.

Ввод: n = 91
Вывод: false
Пояснение: 91 выглядит простым числом, но 7 × 13 = 91. Делитель 7 находится раньше, чем поиск проходит отметку √91 ≈ 9.5.

Дополнительный вопрос

Каждое простое число больше 3 имеет вид 6k-1 или 6k+1. Можешь использовать это, чтобы проверять только треть возможных делителей?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

В определении сказано, что нужно исключить все делители от 2 до n-1, а для наибольшего простого числа это более двух миллиардов делений. Делители образуют пары, произведение которых равно n, и меньший делитель в каждой паре не превышает √n. Поэтому достаточно проверять делители только до √n — не более примерно 23,000 нечётных кандидатов.

Попробуйте каждый делитель

Верно, но не успевает на самых больших тестах

Идея

Определение задаёт алгоритм. Число n ≥ 2 является простым, если ни одно из чисел 2, 3, ..., n-1 не делит его. Проверь каждый возможный делитель d с помощью n % d == 0 и верни false при первом делителе. Для 91 цикл проверяет числа от 2 до 6 и останавливается на 7.

Сначала обработай случай n < 2. При n = 1 диапазон возможных делителей пуст, поэтому цикл никогда не найдёт делитель и сочтёт 1 простым числом.

Цикл обычно быстро останавливается на составных числах, но простое число проходит все проверки, поэтому цикл выполняется до конца. Для n = 2147483647, которое является простым числом, это около 2.1 × 10^9 делений — гораздо больше, чем можно выполнить за несколько секунд.

Алгоритм

Если n < 2, верни false.
Перебери d от 2 до n-1.
Если n % d == 0, верни false.
После цикла верни true.

def isPrime(n):
    if n < 2:
        return False
    for d in range(2, n):
        if n % d == 0:
            return False
    return True

Пробное деление до квадратного корня

Идея

Делители образуют пары. Если d делит n, то и n / d тоже делит его, а их произведение равно n. Они не могут оба быть больше √n, иначе их произведение было бы больше n. Значит, если у n есть делитель, отличный от 1 и самого числа, то найдётся делитель, не превосходящий √n. Для 91 это пара 7 и 13, причём 7 ≤ 9.5. Если ни одно число до √n не делит n, то и ни одно число больше него не делит.

Запишите границу как d * d ≤ n, вместо того чтобы вызывать функцию вычисления квадратного корня. Так вычисления остаются в целых числах, без округления. Знак равенства имеет значение: 49 = 7 × 7, и единственный делитель числа 49 — 7 — находится ровно на √49.

Можно также пропустить половину кандидатов. Отдельно обработайте 2: чётное n является простым только в том случае, если оно равно 2. После этого у нечётного n есть только нечётные делители, поэтому начните с 3 и увеличивайте число на 2. Для n = 2147483647 цикл теперь выполняется около 23,000 раз вместо 2.1 × 10^9.

Алгоритм

Если n < 2, верни false.
Если n чётное, верни результат проверки n == 2.
Начни с d, равного 3, и выполняй цикл, пока d * d ≤ n, используя для d 64-битный тип.
Если n % d == 0, верни false. Иначе прибавь к d 2.
После цикла верни true.

def isPrime(n):
    if n < 2:
        return False
    if n % 2 == 0:
        return n == 2  # 2 is the only even prime
    d = 3
    while d * d <= n:
        if n % d == 0:
            return False
        d += 2
    return True

Ловушки и крайние случаи

Эту идею можно изложить в одной строке. Ошибки возникают на границах: при минимальных входных данных и на последнем делителе.

Возврат true для 1. У него один делитель, а не два, поэтому оно не является простым числом.
Отклонение 2 из-за того, что оно чётное. Проверьте n == 2 до того, как отсеивать чётные числа.
Цикл выполняется, пока d * d < n, вместо ≤. Тогда квадраты простых чисел, таких как 9, 49 и 2147117569 = 46337², проходят проверку как простые числа.
Переполнение в d * d. В 32-битном int значение 46341 × 46341 = 2147488281 не помещается и заворачивается в отрицательное число, поэтому проверка продолжает проходить, а цикл выполняется далеко за пределами √n. Используйте для d 64-битный тип или вместо этого сравнивайте d ≤ n / d.
Получение границы из числа с плавающей запятой sqrt и его усечение. Для любого n здесь значение double точное, но для 64-битных входных данных округление может дать значение на единицу меньше истинного корня и пропустить единственный важный делитель. У d * d ≤ n такого риска нет.

Частые вопросы3

Какова временная сложность проверки того, является ли число простым?

Пробное деление до √n занимает O(√n) времени и O(1) памяти. Для n до 2^31-1 это максимум около 46,000 делений или 23,000, если пропустить чётные делители. Проверка каждого делителя до n-1 имеет сложность O(n) — около двух миллиардов шагов для наибольшего входного значения.

Почему вы проверяете делители только до квадратного корня из n?

Делители образуют пары d и n / d, произведение которых равно n. Если бы оба были больше √n, их произведение было бы больше n. Значит, в каждой паре есть элемент не больше √n, и если до этого момента не обнаружится делитель, то n — простое число.

Является ли 1 простым числом?

Нет. У простого числа ровно два различных делителя: 1 и оно само, а у 1 только один. Если пропустить 1, разложение каждого целого числа на простые множители будет единственным. Вот почему isPrime(1) возвращает false.

def isPrime(n):
    # Напишите код здесь

Тест #1

Тест #2

Тест #3

Аргумент

n = 29

Ожидаемый вывод

true