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).
Функция isPrime для языка Python
Так что я смог решить эту проблему с небольшой помощью из Интернета, и вот что я получил:
Постскриптум Я очень неопытный и только что познакомился с программированием месяц назад: S
27 ответов
Из многих тестов простоты, распространяющихся по Интернету, рассмотрим следующий простой тест:
Рассмотрим простое число 5003:
Строка r = int(n**0.5) имеет значение 70 (квадратный корень из 5003 равен 70.7318881411 и int() усекает это значение)
Из-за первых нескольких тестов и тестов в середине цикла, цикл должен оцениваться только для каждого 6-го числа.
Рассмотрим следующее нечетное число (так как все четные числа, отличные от 2, не простые) 5005, выводится то же самое:
Пределом является квадратный корень, поскольку x*y == y*x функция должна пройти всего 1 цикл, чтобы найти, что 5005 делится на 5 и, следовательно, не является простым. Поскольку 5 X 1001 == 1001 X 5 (и оба по 5005), нам не нужно идти до 1001 в цикле, чтобы знать, что мы знаем в 5!
Теперь давайте посмотрим на алгоритм, который у вас есть:
Я не знаю, опоздал ли я, но я оставлю это здесь, чтобы помочь кому-то в будущем.
Мы используем квадратный корень из (n), то есть 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.
16 = 2 * 8, 4 * 4, 8 * 2.
Вы можете заметить, что после достижения 4, то есть квадратного корня из 16, мы повторили 8 * 2, что мы уже сделали как 2 * 8. Эта модель верна для всех чисел.
Чтобы не повторяться, мы проверяем простоту вплоть до квадратного корня числа n.
Таким образом, мы конвертируем квадратный корень в int, потому что нам не нужен диапазон с плавающими числами.
Прочитайте тест на простоту википедии для получения дополнительной информации.
Проверьте, является ли число простым в Python
Простое число может быть изображено как натуральное число без других положительных делителей, кроме числа 1 и самого себя. Число 1 не учитывается в списке простых чисел.
В этом руководстве будут рассмотрены различные методы, которые вы можете использовать, чтобы проверить, является ли число простым.
Используйте простой метод итерации для определения простого числа в Python
В следующем коде используется метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.
Вы можете оптимизировать приведенный выше код, применив некоторые изменения. Сделайте следующие оптимизации, чтобы сделать код еще быстрее:
Проверяйте, пока не будет достигнут корень данного числа, вместо проверки точного числа. Этот процесс в основном устраняет избыточность, которая возникает, когда больший множитель числа K кратен меньшему множителю, который уже был повторен.
Все простые числа существуют в форме 6n ± 1, за исключением 2 и 3. Следовательно, проверка делимости данного числа на 2 и 3, а затем проверка каждого числа, имеющего форму 6n ± 1, является более эффективным решением.
В следующем коде используется оптимизированный метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.
Оптимизированный метод итерации делает его быстрее и эффективнее, чем простой метод итерации, примерно на 30%.
Следует отметить, что любое отрицательное число не подпадает под критерии простых чисел. Вывод этих функций может измениться, если ему сопоставить какое-либо отрицательное число.
Функция isPrime для языка Python
Итак, я смог решить эту проблему с небольшой помощью из Интернета, и вот что я получил:
Но мой вопрос действительно в том, как это сделать, но ПОЧЕМУ. Я понимаю, что 1 не считается «простым» числом, даже если это так, и я понимаю, что если оно делится на НИЧЕГО в пределах диапазона, оно автоматически не является простым числом, поэтому возвращается оператор False. но мой вопрос Какую роль здесь играет укоренение «n»?
P.s. Я очень неопытен и только месяц назад познакомился с программированием.
Рассмотрим простое число 5003:
Линия r = int(n**0.5) оценивается как 70 (квадратный корень из 5003 равен 70,7318881411 и int() обрезает это значение)
Рассмотрим следующее нечетное число (поскольку все четные числа, кроме 2, не являются простыми) 5005, то же самое напечатает:
Теперь посмотрим на алгоритм, который у вас есть:
Алгоритм, который я использовал is_prime примерно в 2 раза быстрее, так как только каждое шестое целое число проходит через цикл. (Я снова проверил его.)
Рассмотрим число 20; целые множители: 1, 2, 4, 5, 10 и 20. Когда вы делите 20 на 2 и получаете 10, вы знаете, что оно также делится на 10, без необходимости проверки. Когда вы делите его на 4 и получаете 5, вы знаете, что оно делится как на 4, так и на 5, без необходимости проверять 5.
После достижения этой середины в факторах у вас больше не будет чисел для проверки, которые вы еще не распознали как факторы ранее. Следовательно, вам нужно пройти только половину пути, чтобы увидеть, является ли что-то простым, и эту половину пути можно найти, взяв квадратный корень из числа.
Ниже не выполняются операции с плавающей запятой. Это быстрее и допускает более высокие аргументы. Причина, по которой вы должны использовать только квадратный корень, заключается в том, что если число имеет множитель больше, чем его квадратный корень, оно также имеет множитель меньше него.
Вопрос был задан немного назад, но у меня есть более короткое решение для вас
Математическая операция в большинстве случаев возвращает 2, если число является простым, а не 2. Но если заданное число 2, оно добавляется к списку, в котором мы изучаем.
isNotPrime () надежно возвращает True, если Number не является простым.
Этот метод будет медленнее, чем рекурсивные и перечисляющие методы здесь, но использует теорему Вильсона и представляет собой всего одну строку:
Находить квадратный корень из числа нужно для повышения эффективности. например. Если я пытаюсь найти множители 36, наибольшее число, которое можно умножить само на себя, чтобы получить 36, будет 6. 7 * 7 = 49.
поэтому каждый множитель 36 нужно умножить на 6 или меньшее число.
и вот как его использовать
Чтобы найти все простые числа, которые вы можете использовать:
Обратите внимание, что 5 в этом случае обозначает количество простых чисел, которые необходимо найти, и максимальный диапазон 4000, в котором будут искать простые числа.
Я не знаю, опаздываю ли я, но я оставлю это здесь, чтобы помочь кому-то в будущем.
Мы используем квадратный корень из (n), т.е. 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, потому что нам не нужен диапазон с плавающими числами.
Прочтите тест на простоту в Википедии для получения дополнительной информации.
Чтобы ответить на исходный вопрос, п ** 0,5 такой же как квадрат корня из n. Вы можете прекратить проверку факторов после этого числа, потому что составное число будет всегда имеют множитель, меньший или равный его квадратному корню. Это быстрее, чем, скажем, просто проверять все множители от 2 до n для каждого n, потому что мы проверяем меньше чисел, что экономит больше времени при увеличении n.
Реализовал псевдокод (https://en.wikipedia.org/wiki/Primality_test) в python, надеюсь, это поможет.
Если вы хотите выглядеть настоящим умником, используйте следующую однострочную функцию:
Объяснение «волшебного регулярного выражения» можно найти здесь.
Истинно, если число простое, иначе ложно
И ПОЧЕМУ мы это делаем? Возьмем, к примеру, число 400: мы можем представить его в виде a * b
У меня есть новое решение, которое, я думаю, может быть быстрее, чем любая из упомянутых функций в 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.
(https://www.youtube.com/watch?v=Vxw1b8f_yts&t=3384s) Авинаш Джайн
6 Best Ways To Check If a Number Is Prime Or Not in Python
This article will learn how to check if a number is prime or not in Python. Usually, we all know some common methods using library functions or without using library functions. But how many of us know that there are 6 ways to check a prime number. Maybe some of us will be familiar with some methods. But this article will teach you all the possible ways. Let us move on to check if a number is prime or not.
In the number system, we have two types of numbers. They are Prime and composite. Prime numbers are the numbers that are not the product of any other numbers. These numbers are always natural numbers. For example, 13 is a prime number. Because we cannot get this number as a product of any other two numbers except to the product of 1, on the other hand, if we take 4, it will show a result as a composite because it is a product of 2X2. I hope now all are clear about prime numbers.
The following methods are available:
Method 1: Using isprime() to check if a number is prime or not in python
1.1 Code
This method is implemented using function. It will return True if the number is prime. Otherwise, it will return False. First checking with 7 and then with 8.
Output
1.2 Code
This method is implemented using function. It will return True if the number is prime. Otherwise, it will return False. First checking with 13 and then with 18.
Output
1.3 Code
This method is implemented using function. It will return True if the number is prime. Otherwise, it will return False. First checking with 15 and then with 2.
Output
1.4 Code
This method is implemented using function. It will return True if the number is prime. Otherwise, it will return False—first checking with 64 and then with 5.
Output
1.5 Code
This method is implemented using function. It will return True if the number is prime. Otherwise, it will return False—first checking with 64 and then with 5.
Output
Method 2: Using if-else statements to check if a number is prime or not
This code is normally using loops. Here we are getting a number as an input from the user. It performs the code and gives the result to the user. If the user gives 1 as an input, it will display neither prime nor composite.
Output
Method 3: Using math function to check if a number is prime or not
Math is a module that is already available in the python library. This module contains a lot of mathematical functions. To access this module, we have to import the module as:
Here we are using math.sqrt to check if the number is prime or not. sqrt() is a built-in function in python.
Syntax
Parameter
x – that can be any value.
