isprime python функция что делает

Проверьте, является ли число простым в Python

Простое число может быть изображено как натуральное число без других положительных делителей, кроме числа 1 и самого себя. Число 1 не учитывается в списке простых чисел.

В этом руководстве будут рассмотрены различные методы, которые вы можете использовать, чтобы проверить, является ли число простым.

Используйте простой метод итерации для определения простого числа в Python

В следующем коде используется метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.

Вы можете оптимизировать приведенный выше код, применив некоторые изменения. Сделайте следующие оптимизации, чтобы сделать код еще быстрее:

Проверяйте, пока не будет достигнут корень данного числа, вместо проверки точного числа. Этот процесс в основном устраняет избыточность, которая возникает, когда больший множитель числа K кратен меньшему множителю, который уже был повторен.

Все простые числа существуют в форме 6n ± 1, за исключением 2 и 3. Следовательно, проверка делимости данного числа на 2 и 3, а затем проверка каждого числа, имеющего форму 6n ± 1, является более эффективным решением.

В следующем коде используется оптимизированный метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.

Оптимизированный метод итерации делает его быстрее и эффективнее, чем простой метод итерации, примерно на 30%.

Следует отметить, что любое отрицательное число не подпадает под критерии простых чисел. Вывод этих функций может измениться, если ему сопоставить какое-либо отрицательное число.

Источник

Функция isPrime для языка Python

Итак, я смог решить эту проблему с небольшой помощью из Интернета, и это то, что я получил:

Но мой вопрос действительно в том, как это сделать, но ПОЧЕМУ. Я понимаю, что 1 не считается «простым» числом, даже если это так, и я понимаю, что если он делит на НИЧЕГО в пределах диапазона, он автоматически является простым, таким образом, возвратом False. но мой вопрос какую роль играет квадрат «n» здесь? Большое спасибо за внимание.

P.s. Я очень неопытен и только что был введен в программирование месяц назад: S

26 ответов

Во многих тестах primality, плавающих вокруг Интернета, рассмотрите следующий простой тест:

Рассмотрим простое число 5003:

Линия r = int(n**0.5) оценивается до 70 (квадратный корень из 5003 равен 70.7318881411, а int() обрезает это значение)

Из-за первых нескольких тестов и тестов в середине цикла цикл нужно только оценивать каждые 6-е число.

Рассмотрим следующее нечетное число (поскольку все четные числа, отличные от 2, не являются первыми) из 5005, то же самое печатает:

Теперь посмотрим на алгоритм, который у вас есть:

С n**.5 вы не занимаете квадрат n, а получаете квадратный корень.

Рассмотрим число 20; целые коэффициенты равны 1, 2, 4, 5, 10 и 20. Когда вы разделите 20 на 2 и получите 10, вы знаете, что он также делится на 10, без необходимости проверять. Когда вы разделите его на 4 и получите 5, вы знаете, что он делится на 4 и 5, без необходимости проверять 5.

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

Кроме того, причина 1 не является простым числом, так как простые числа определяются как имеющие 2 фактора, 1 и себя. то есть 2 1 * 2, 3 равно 1 * 3, 5 равно 1 * 5. Но 1 (1 * 1) имеет только один фактор. Поэтому оно не соответствует этому определению.

isPrime() возвращает True, если Number является Prime, а False, если нет.

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

Поиск квадратного корня из числа для эффективности. например. если я пытаюсь найти коэффициенты 36, то наибольшее число, которое может быть умножено на себя на форму 36, равно 6. 7 * 7 = 49.

поэтому каждый коэффициент 36 должен умножаться на 6 или меньшее число.

Этот метод будет медленнее, чем рекурсивные и перечислительные методы, но использует теорему Вильсона и представляет собой одну строку:

Я не знаю, опаздываю ли я, но я оставлю это здесь, чтобы помочь кому-то в будущем.

Мы используем квадратный корень из (n) i.e int (n ** 0.5), чтобы уменьшить диапазон чисел, которые ваша программа будет вынуждена вычислять.

Например, мы можем выполнить пробное деление, чтобы проверить простоту 100. Посмотрим на все делители 100:

2, 4, 5, 10, 20, 25, 50 Здесь мы видим, что наибольший коэффициент равен 100/2 = 50. Это справедливо для всех n: все делители меньше или равны n/2. Если мы более подробно рассмотрим дивизоров, мы увидим, что некоторые из них являются избыточными. Если мы будем писать список по-разному:

100 = 2 × 50 = 4 × 25 = 5 × 20 = 10 × 10 = 20 × 5 = 25 × 4 = 50 × 2 избыточность становится очевидной. Как только мы достигнем 10, что составляет √100, делители просто поворачиваются и повторяются. Поэтому мы можем дополнительно исключить тестовые дивизоры, превышающие √n.

Возьмите еще одно число, например 16.

Его делители равны 2,4,8

16 = 2 * 8, 4 * 4, 8 * 2.

Вы можете заметить, что после достижения 4, который является квадратным корнем из 16, мы повторили 8 * 2, которые мы уже сделали как 2 * 8. Этот шаблон справедлив для всех чисел.

Чтобы избежать повторения, мы, таким образом, проверяем, что приматность до квадратного корня из числа n.

Итак, мы преобразуем квадратный корень в int, потому что нам не нужен диапазон с плавающими числами.

Прочтите тест primality на wikipedia для получения дополнительной информации.

Источник

Интервью на Python: Простые числа

Напишите программу, чтобы составить список всех простых чисел меньше 20. Перед началом важно отметить, что такое простое число. Простое число должно быть положительным целым числом, делящимся ровно на 2 целых числа (1 и само по себе) 1 не является простым числом, хотя существует множество различных способов решения этой проблемы, вот несколько различных подходов.

Напишите программу, чтобы составить список всех простых чисел меньше 20.

Прежде чем начать, важно отметить, что такое простое число.

Хотя существует множество различных способов решения этой проблемы, вот несколько различных подходов.

Подход 1: Для петель

Если вы посмотрите на внутренний цикл for, заключенный в красный прямоугольник ниже, обратите внимание, что, как только isPrime имеет значение False, продолжать итерацию неэффективно. Было бы более эффективно выйти из цикла.

Подход 2: Для петель с разрывом

Подход 3: Для цикла, разрыва и квадратного корня

Сравнение во времени различных подходов

Некоторые методы генерации простых чисел более эффективны. Чтобы показать это, давайте изучим разницу в производительности между подходами, генерирующими простые числа до заданного числа.

Подход 1: Для петель

Подход 2: Для петель с разрывом

Подход 3: Для цикла, разрыва и квадратного корня

Очевидно, что подход 3 является самым быстрым.

Заключительные замечания

Эта статья первоначально появилась в моем блоге medium

Источник

IsPrime Функция для языка Python

Итак, я смог решить эту проблему с небольшой помощью из Интернета, и это то, что я получил:

Но мой вопрос действительно в том, как это сделать, но ПОЧЕМУ. Я понимаю, что 1 не считается «простым» числом, даже если это так, и я понимаю, что если он делит на НИЧЕГО в пределах диапазона, он автоматически является простым, таким образом, возвратом False. но мой вопрос какую роль играет квадрат «n» здесь? Большое спасибо за внимание.

P.s. Я очень неопытен и только что был введен в программирование месяц назад: S

Во многих тестах primality, плавающих вокруг Интернета, рассмотрите следующий простой тест:

Рассмотрим простое число 5003:

Линия r = int(n**0.5) оценивается до 70 (квадратный корень из 5003 равен 70.7318881411, а int() обрезает это значение)

Из-за первых нескольких тестов и тестов в середине цикла цикл нужно только оценивать каждые 6-е число.

Рассмотрим следующее нечетное число (поскольку все четные числа, отличные от 2, не являются первыми) из 5005, то же самое печатает:

Теперь посмотрим на алгоритм, который у вас есть:

Он не проверяет, если n меньше 2, и нет простых чисел меньше 2;
Он проверяет каждое число между 2 и n ** 0.5, включая все четные и все нечетные числа. Поскольку каждое число, большее 2, которое делится на 2, не является простым, мы можем немного ускорить его, только проверяя нечетные числа больше 2.

С n**.5 вы не занимаете квадрат n, а получаете квадратный корень.

Рассмотрим число 20; целые коэффициенты равны 1, 2, 4, 5, 10 и 20. Когда вы разделите 20 на 2 и получите 10, вы знаете, что он также делится на 10, без необходимости проверять. Когда вы разделите его на 4 и получите 5, вы знаете, что он делится на 4 и 5, без необходимости проверять 5.

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

Кроме того, причина 1 не является простым числом, так как простые числа определяются как имеющие 2 фактора, 1 и себя. то есть 2 1 * 2, 3 равно 1 * 3, 5 равно 1 * 5. Но 1 (1 * 1) имеет только один фактор. Поэтому оно не соответствует этому определению.

Источник

IsPrime Функция для языка Python

Итак, я смог решить эту проблему с небольшой помощью из Интернета, и это то, что я получил:

Но мой вопрос действительно в том, как это сделать, но ПОЧЕМУ. Я понимаю, что 1 не считается «простым» числом, даже если это так, и я понимаю, что если он делит на НИЧЕГО в пределах диапазона, он автоматически является простым, таким образом, возвратом False. но мой вопрос какую роль играет квадрат «n» здесь? Большое спасибо за внимание.

P.s. Я очень неопытен и только что был введен в программирование месяц назад: S

ОТВЕТЫ

Ответ 1

Во многих тестах primality, плавающих вокруг Интернета, рассмотрите следующий простой тест:

Рассмотрим простое число 5003:

Линия r = int(n**0.5) оценивается до 70 (квадратный корень из 5003 равен 70.7318881411, а int() обрезает это значение)

Из-за первых нескольких тестов и тестов в середине цикла цикл нужно только оценивать каждые 6-е число.

Рассмотрим следующее нечетное число (поскольку все четные числа, отличные от 2, не являются первыми) из 5005, то же самое печатает:

Теперь посмотрим на алгоритм, который у вас есть:

Ответ 2

С n**.5 вы не занимаете квадрат n, а получаете квадратный корень.

Рассмотрим число 20; целые коэффициенты равны 1, 2, 4, 5, 10 и 20. Когда вы разделите 20 на 2 и получите 10, вы знаете, что он также делится на 10, без необходимости проверять. Когда вы разделите его на 4 и получите 5, вы знаете, что он делится на 4 и 5, без необходимости проверять 5.

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

Кроме того, причина 1 не является простым числом, так как простые числа определяются как имеющие 2 фактора, 1 и себя. то есть 2 1 * 2, 3 равно 1 * 3, 5 равно 1 * 5. Но 1 (1 * 1) имеет только один фактор. Поэтому оно не соответствует этому определению.

Ответ 3

isPrime() возвращает True, если Number является Prime, а False, если нет.

Ответ 4

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

Ответ 5

Поиск квадратного корня из числа для эффективности. например. если я пытаюсь найти коэффициенты 36, то наибольшее число, которое может быть умножено на себя на форму 36, равно 6. 7 * 7 = 49.

поэтому каждый коэффициент 36 должен умножаться на 6 или меньшее число.

Ответ 6

Ответ 7

Этот метод будет медленнее, чем рекурсивные и перечислительные методы, но использует теорему Вильсона и представляет собой одну строку:

Ответ 8

Ответ 9

и вот как его использовать

Чтобы найти все простые числа, которые вы могли бы использовать:

Обратите внимание, что в этом случае 5 обозначает число простых чисел, которое можно найти, и 4000 max диапазона, где будут искать простые числа.

Ответ 10

Ответ 11

Я не знаю, опаздываю ли я, но я оставлю это здесь, чтобы помочь кому-то в будущем.

Мы используем квадратный корень из (n) i.e int (n ** 0.5), чтобы уменьшить диапазон чисел, которые ваша программа будет вынуждена вычислять.

Например, мы можем выполнить пробное деление, чтобы проверить простоту 100. Посмотрим на все делители 100:

2, 4, 5, 10, 20, 25, 50 Здесь мы видим, что наибольший коэффициент равен 100/2 = 50. Это справедливо для всех n: все делители меньше или равны n/2. Если мы более подробно рассмотрим дивизоров, мы увидим, что некоторые из них являются избыточными. Если мы будем писать список по-разному:

100 = 2 × 50 = 4 × 25 = 5 × 20 = 10 × 10 = 20 × 5 = 25 × 4 = 50 × 2 избыточность становится очевидной. Как только мы достигнем 10, что составляет √100, делители просто поворачиваются и повторяются. Поэтому мы можем дополнительно исключить тестовые дивизоры, превышающие √n.

Возьмите еще одно число, например 16.

Его делители равны 2,4,8

16 = 2 * 8, 4 * 4, 8 * 2.

Вы можете заметить, что после достижения 4, который является квадратным корнем из 16, мы повторили 8 * 2, которые мы уже сделали как 2 * 8. Этот шаблон справедлив для всех чисел.

Чтобы избежать повторения, мы, таким образом, проверяем, что приматность до квадратного корня из числа n.

Итак, мы преобразуем квадратный корень в int, потому что нам не нужен диапазон с плавающими числами.

Прочтите тест primality на wikipedia для получения дополнительной информации.

Ответ 12

Чтобы ответить на исходный вопрос, n ** 0,5 совпадает с квадратом корня n. Вы можете остановить проверку факторов после этого числа, потому что составное число всегда будет иметь коэффициент меньше или равен его квадратному корню. Это быстрее, чем просто проверка всех факторов между 2 и n для каждого n, поскольку мы проверяем меньшее количество чисел, что экономит больше времени с ростом n.

Ответ 13

Ответ 14

Реализовано псевдокод (https://en.wikipedia.org/wiki/Primality_test) в python, надеюсь, что эта помощь.

Ответ 15

Если вы хотите выйти в качестве реального смартфона, используйте следующую однострочную функцию:

Объяснение «волшебного регулярного выражения» можно найти здесь

Ответ 16

Истинно, если число является простым, иначе false

Ответ 17

Ответ 18

Ответ 19

Это было упражнение в codecademy и вот как я прошел его ниже.

Ответ 20

Ответ 21

Ответ 22

А, (n ** 0,5) → Это даст нам » квадратный корень» из «n». Поскольку он «n поднят до мощности 0,5 или 1/2»

И ПОЧЕМУ мы это делаем, Возьмем, например, номер 400: Мы можем представить его в виде a * b

Квадратный корень 400 составляет 20: и мы можем видеть, что нам нужно всего лишь проверить делимость до 20, потому что, поскольку ‘a’ достигает 20 ‘b’, начинает уменьшаться. Итак, в конечном счете мы проверяем делимость с числами меньше квадратного корня.

Ответ 23

У меня есть новое решение, которое, я думаю, может быть быстрее любого из упомянутых Функция в Python

Это основано на идее, что: N/D = R для любого произвольного числа N наименьшее возможное число для деления N (если не простое) равно D = 2, а соответствующий результат R равен (N/2) (самый высокий).

По мере того как D больше, результат R становится меньше ex: делят на D = 3 результаты R = (N/3) поэтому, когда мы проверяем, является ли N делимым на D, мы также проверяем, делится ли он на R

так как D больше, а R меньше, чем (D == R == квадратный корень (N))

тогда нам нужно только проверить числа от 2 до sqrt (N) еще один совет, чтобы сэкономить время, нам нужно только проверить нечетные числа, так как он делится на любое четное число, он также будет делиться на 2.

поэтому последовательность будет 3,5,7,9. sqrt (N).

Источник