Как определить что число простое питон
Python Exercise: проверить число простое или нет
Python Exercises, Practice and Solution: Write a Python function that takes a number as a parameter and check the number is prime or not.
Пример
def is_prime(a): if a 8 ответов
Вот мой взгляд на проблему:
from math import sqrt; from itertools import count, islicedef isPrime(n): return n > 1 and all(n%i for i in islice(count(2), int(sqrt(n)-1)))
#1 Дек. 23, 2011 22:41:12
Определение простое число или нет
i=2.000
while x>i:
if x%i!=0:
i=i+1
print “prostoe”
else:
print “ne prostoe”
break
логически я понимаю так, перебирал разные варианты, но нужного результата нет(((( В какую сторону копать? Направте плиз! Или хотябы логику скажите, как оно должно работать. Спасибо!
Отредактировано (Дек. 23, 2011 22:58:02)
#2 Дек. 23, 2011 23:33:21
Определение простое число или нет
Описание
Я дам вам некоторые подробности об этой почти эзотерической единственной строке кода, которая проверит простые числа:
xrange(2147483647+1) # OverflowErrorfrom itertools import count, islicecount(1) # Count from 1 to infinity with step=+1islice(count(1), 2147483648) # Count from 1 to 2^31 with step=+1islice(count(1, 3), 2147483648) # Count from 1 to 3*2^31 with step=+3
Давайте найдем все делители n = 100 и перечислим их в таблицу:
2 x 50 = 100 4 x 25 = 100 5 x 20 = 10010 x 10 = 100 #5 Дек. 25, 2011 02:18:08
Определение простое число или нет
Будет работать заметно быстрее, если этот цикл заменить на:
Проверьте, является ли число простым в Python
Простое число может быть изображено как натуральное число без других положительных делителей, кроме числа 1 и самого себя. Число 1 не учитывается в списке простых чисел.
В этом руководстве будут рассмотрены различные методы, которые вы можете использовать, чтобы проверить, является ли число простым.
Используйте простой метод итерации для определения простого числа в Python
В следующем коде используется метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.
Вы можете оптимизировать приведенный выше код, применив некоторые изменения. Сделайте следующие оптимизации, чтобы сделать код еще быстрее:
Проверяйте, пока не будет достигнут корень данного числа, вместо проверки точного числа. Этот процесс в основном устраняет избыточность, которая возникает, когда больший множитель числа K кратен меньшему множителю, который уже был повторен.
Все простые числа существуют в форме 6n ± 1, за исключением 2 и 3. Следовательно, проверка делимости данного числа на 2 и 3, а затем проверка каждого числа, имеющего форму 6n ± 1, является более эффективным решением.
В следующем коде используется оптимизированный метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.
Оптимизированный метод итерации делает его быстрее и эффективнее, чем простой метод итерации, примерно на 30%.
Следует отметить, что любое отрицательное число не подпадает под критерии простых чисел. Вывод этих функций может измениться, если ему сопоставить какое-либо отрицательное число.
Проверка числа на простоту
Проверка числа на простоту
Всем доброго времени суток! Пишу тест Лемана на проверку простое число или нет. Выдает ошибку на 21.
Проверка числа на простоту
Подскажите пожалуйста, как проверить, что число является не простым
Проверка числа на простоту
Помогите написать программу которая проверяет простое число или нет.
Проверка числа на простоту
Почему, если необ. проверить, является ли число простым(напр. ч-ло n),можно просматривать делители.
Решение
Anarom, если вбить в тестировщик 2 выдаёт неверный ответ, и решение нужно при помощи рекурсии сделать, но спасибо
Добавлено через 2 минуты
Garry Galler, для меня такое решение пока слишком сложное, некоторые вещи мы ещё не проходили, да и в тестировщике выдаёт Runtime error
Вот, к примеру, решение №1 прекрасно справляется с числами в 100 млрд.
Пожалуйста выложи полный код этой программы, очень нужно!
Добавлено через 1 минуту
пожалуйста, вышлите полный ответ на задачу
Добавлено через 34 секунды
пожалуйста, пришли полный ответ на эту задачу
Марк Лутц утверждает, что рекурсия ограничена только объемом памяти на компьютере.
А вот подтверждение этому самим Python’ом этого:
>>> help(sys.setrecursionlimit)
Help on built-in function setrecursionlimit in module sys:
Set the maximum depth of the Python interpreter stack to n. This
limit prevents infinite recursion from causing an overflow of the C
stack and crashing Python. The highest possible limit is platform-
dependent.
Установите максимальную глубину стека интерпретатора Python в n. Это
limit предотвращает бесконечную рекурсию от переполнения C
стек и сбой Python. Максимально возможное ограничение-платформа-
зависимый.
Программа Python для проверки того, является ли число простым или нет
Факторы числа:
Когда два целых числа умножаются, получается произведение. Факторы продукта – это числа, которые мы умножаем.
В математике коэффициент – это число или алгебраическое выражение, которое поровну делит другое число или выражение, не оставляя остатка.
Простое число:
Простое число – это положительное целое число больше 1, не имеющее других переменных, кроме 1 и самого числа. Поскольку у них нет других переменных, числа 2, 3, 5, 7 и т. Д. Являются простыми числами.
Учитывая число, задача состоит в том, чтобы проверить, является ли данное число простым или нет.
Примеры:
Пример 1:
Вход:
Выход:
Пример 2:
Вход:
Выход:
Программа для проверки простого числа в программировании на Python
Ниже приведены способы проверить, является ли данное число простым или нет:
Изучите больше примеров, связанных с концепциями Python, из Руководства по примерам программирования Python и получите повышение от новичка до профессионального уровня программиста в языке программирования Python.
1) Использование цикла for для перехода от 2 к N-1 с использованием флаговой или временной переменной
Чтобы увидеть, есть ли какие-либо положительные делители, кроме 1 и самого числа, мы делим входное число на все числа в диапазоне от 2 до (N – 1).
Если делитель найден, отображается сообщение «число не является простым числом», в противном случае отображается сообщение «число является простым числом».
Мы выполняем итерацию от 2 до N-1, используя цикл for.
Ниже представлена реализация:
Выход:
Объяснение:
В этой программе мы проверяли, является ли число простым или нет. Простые числа – это не те, которые меньше или равны единице. В результате мы идем вперед, только если число больше единицы.
Мы проверяем, делится ли число в точности на любое число от 2 до числа – 1. Мы устанавливаем temp равным True и прерываем цикл, если найдем множитель в этом диапазоне, указывающий, что число не является простым.
Мы проверяем, является ли temp истинным или ложным вне цикла.
Число не является простым числом, если оно истинно.
Если False, данное число является простым числом.
2) Использование оператора For Else
Чтобы проверить, является ли число простым, мы использовали аргумент for… else.
Он основан на логике, согласно которой оператор else цикла for выполняется тогда и только тогда, когда цикл for не прерывается. Только когда переменные не найдены, выполняется условие, указывающее, что данное число является простым.
В результате мы печатаем, что число простое в предложении else.
Ниже представлена реализация:
Выход:
3) Ограничения вышеперечисленных методов с точки зрения временной сложности
В этих двух методах цикл идет от 2 до номера N-1.
Следовательно, мы можем сказать, что временная сложность вышеупомянутых методов составляет O (n).
Что делать, если число очень большое?
Как и 10 ^ 18, выполнение вышеуказанных методов занимает почти 31 год.
Тогда как этого избежать?
Мы видим, что множители чисел существуют от 1 до N / 2, за исключением самого числа.
Но это также занимает около 15 лет.
Таким образом, мы выполняем цикл до квадратного корня из N в следующем методе, который дает временную сложность O (Sqrt (n)).
4) Подход к решению для эффективного подхода
Мы улучшим нашу программу, сократив диапазон чисел, в котором мы ищем факторы.
Наш диапазон поиска в приведенной выше программе – от 2 до числа – 1.
Должен был использоваться набор, диапазон (2, число / 2) или диапазон (2, math.floor (math.sqrt (число)). Последний диапазон основан на требовании, чтобы коэффициент составного числа был меньше его квадрата. корень. В противном случае это простое число.
5) Внедрение эффективного подхода
В этой функции мы используем математическую библиотеку Python для вычисления целого числа max_divisor, которое является квадратным корнем из числа, и получения его минимального значения. В последнем примере мы выполняем итерацию от 2 до n-1. Однако в этом случае мы уменьшаем делители вдвое, как показано. Чтобы получить функции floor и sqrt, вам необходимо импортировать модуль math.
Подход:
Ниже представлена реализация:
Анализ различных методов, чтобы найти простое число в Python
Если вы участвуете в соревновательном программировании, вам может быть знаком тот факт, что вопросы, связанные с простыми числами, являются одним из вариантов решения проблем. Здесь мы обсудим, как оптимизировать вашу функцию, которая проверяет простое число в данном наборе диапазонов, а также рассчитаем время для их выполнения.
По определению, простое число — это положительное целое число, которое делится только на себя и 1. Например: 2,3,5,7. Но если число можно разбить на меньшие числа, оно называется составным числом. Например: 4 = 2 * 2, 6 = 2 * 3
И целое число 1 не является ни простым числом, ни составным числом. Проверить, что число простое, легко, но эффективная проверка требует некоторых усилий.
Способ 1
Давайте теперь перейдем к самой первой функции, чтобы проверить, является ли число, скажем, n, простым или нет. В этом методе мы проверим все делители от 2 до n-1. Мы пропустим 1 и n. Если n делится на любой из делителей, функция вернет False, иначе True.
Ниже приведены шаги, используемые в этом методе:
# Программа Python для поиска простых чисел в диапазоне
c = 0 # для подсчета
В приведенном выше коде мы проверяем все числа от 1 до 100000, являются ли эти числа простыми или нет. У этого есть огромное время выполнения, как показано. Это займет около 1 минуты, чтобы бежать. Это простой подход, но он требует много времени для запуска. Таким образом, это не является предпочтительным в конкурентном программировании.
Способ 2
В этом методе мы используем простой прием, уменьшая количество проверяемых делителей. Мы обнаружили, что есть тонкая линия, которая действует как зеркало, что показывает факторизацию под линией и факторизацию над линией в обратном порядке. Линия, которая разделила факторы на две половины, является линией квадратного корня числа. Если число является идеальным квадратом, мы можем сдвинуть линию на 1, и если мы можем получить целочисленное значение линии, которая делится.
В этой функции мы вычисляем целое число, скажем, max_div, которое является квадратным корнем числа, и получаем его минимальное значение, используя математическую библиотеку Python. В последнем примере мы повторяем от 2 до n-1. Но в этом мы уменьшаем делители наполовину, как показано. Вам нужно импортировать математический модуль, чтобы получить функцию floor и sqrt.
Ниже приведены шаги, используемые в этом методе:
# Программа Python для поиска простых чисел в диапазоне
c = 0 # для подсчета
В приведенном выше коде мы проверяем все числа от 1 до 100000, являются ли эти числа простыми или нет. Это занимает сравнительно меньше времени, чем предыдущий метод. Это немного хитрый подход, но он имеет огромное значение во время выполнения кода. Так что это предпочтительнее в конкурентном программировании.
Способ 3
Теперь мы оптимизируем наш код до следующего уровня, который занимает меньше времени, чем предыдущий метод. Вы могли заметить, что в последнем примере мы повторяли каждое четное число до предела, который был пустой тратой. Следует отметить, что все четные числа, кроме двух, не могут быть простыми числами. В этом методе мы выбрасываем все четные числа для оптимизации нашего кода и проверяем только нечетные делители.
Ниже приведены шаги, используемые в этом методе:
# Программа Python для поиска простых чисел в диапазоне
if n > 2 and n % 2 = = 0 :
c = 0 # для подсчета
В приведенном выше коде мы проверяем все числа от 1 до 100000, являются ли эти числа простыми или нет. Это занимает сравнительно меньше времени, чем все предыдущие методы запуска программы. Это самый эффективный и быстрый способ проверить простое число. Поэтому он наиболее предпочтителен в конкурентном программировании. В следующий раз, пытаясь ответить на любой вопрос в конкурентном программировании, используйте этот метод для достижения наилучших результатов.
Метод сита
Этот метод печатает все простые числа, меньшие или равные данному числу, n. Например, если n равно 10, вывод должен быть «2, 3, 5, 7». Если n равно 20, выходное значение должно быть «2, 3, 5, 7, 11, 13, 17, 19».
Этот метод считается наиболее эффективным методом для генерации всех простых чисел, меньших заданного числа, n. Он считается самым быстрым из всех способов генерирования списка простых чисел. Этот метод не подходит для проверки определенного номера. Этот метод предпочтителен для генерации списка всех простых чисел.
# Программа Python для поиска простых чисел в диапазоне
# Создайте логический массив «prime [0..n]» и
# инициализировать все записи, как истина. Ценность
# в простом [i] будет, наконец, ложным, если я
# Не простое, иначе правда.
prime = [ True for i in range (n + 1 )]
# Если простое число [p] не изменилось, то оно
# Обновить все кратные р
# Распечатать все простые числа
c = SieveOfEratosthenes( 100000 )
Примечание. Время, необходимое для всех процедур, может варьироваться в зависимости от компилятора, но порядок времени, необходимый для различных методов, останется неизменным.
Пожалуйста, пишите комментарии, если вы обнаружите что-то неправильное, или вы хотите поделиться дополнительной информацией по обсуждаемой выше теме.