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 .

Q: Есть ли более быстрый способ проверять, являются ли очень большие числа простыми?

Для одного 32-битного числа пробное деление до √n достаточно быстрое. Для чисел с десятками цифр программы используют тест Миллера — Рабина, который проверяет несколько степеней по модулю вместо перебора делителей. Чтобы перечислить все простые числа до заданного предела, решето Эратосфена эффективнее, чем проверка каждого числа по отдельности.

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

+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.

+15 скрытых тестов при отправке

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

Каждое простое число больше 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 такого риска нет.

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

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

Пробное деление до √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.

Есть ли более быстрый способ проверять, являются ли очень большие числа простыми?

Для одного 32-битного числа пробное деление до √n достаточно быстрое. Для чисел с десятками цифр программы используют тест Миллера — Рабина, который проверяет несколько степеней по модулю вместо перебора делителей. Чтобы перечислить все простые числа до заданного предела, решето Эратосфена эффективнее, чем проверка каждого числа по отдельности.

Python

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

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

n = 29

Ожидается

true