Как найти простое число в списке?
Как можно найти простыe числa в последовательности десятичных, целых, отрицательных чисел и слов? я попробовал решить это таким образом:
и в данном примере выдает True, хотя 2.24 не простое число, то есть программа не рабочая и считает десятичные, отрицательные числа ВСЕ без исключения за простые
А также выдает ошибку, когда встречает слово типа str()
проверить число на соответствие типу int
получить значение по модулю:
искать делители от 2 до math.sqrt(n)
если не найдены — число простое
на счет отрицательных чисел — один момент с одной стороны конечно по определению простое число — это натуральное число строго большее 1, так что по идее надо проверку такую:
и не париться с абсолютным значением, но иногда приходилось считать и отрицательные простыми числами (при использовании основной теоремы арифметики), вернее не считать, а использовать отрицательные как простые при разложении
хотя для не целых чисел я бы все таки выбрасывал исключение — логически наверное более правильно это
P.S.
кстати для простого числа есть и другое определение для которого код будет вот таким коротким, без проверки на 1 и отрицательные числа:
Проверьте, является ли число простым в Python
Простое число может быть изображено как натуральное число без других положительных делителей, кроме числа 1 и самого себя. Число 1 не учитывается в списке простых чисел.
В этом руководстве будут рассмотрены различные методы, которые вы можете использовать, чтобы проверить, является ли число простым.
Используйте простой метод итерации для определения простого числа в Python
В этом методе мы используем простой метод итерации с использованием цикла for или while . Переберите числа, начиная с 2 и далее до K/2 , и проверьте, делит ли какое-либо из этих чисел K .
Если найдено число, соответствующее этому критерию, то возвращается False . С другой стороны, если все числа не соответствуют этому критерию, данное число K является простым числом, и возвращается значение True .
В следующем коде используется метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.
Проверяйте, пока не будет достигнут корень данного числа, вместо проверки точного числа. Этот процесс в основном устраняет избыточность, которая возникает, когда больший множитель числа K кратен меньшему множителю, который уже был повторен.
В следующем коде используется оптимизированный метод простой итерации, чтобы проверить, является ли данное число простым числом в Python.
Оптимизированный метод итерации делает его быстрее и эффективнее, чем простой метод итерации, примерно на 30%.
Используйте функцию sympy.isprime() , чтобы проверить, является ли данное число простым числом в Python
SymPy — это библиотека на Python, используемая для реализации символьной математики. Это упрощенная система компьютерной алгебры (CAS), которая содержит все основные функции. Для этого метода необходима установка этого модуля, и его можно загрузить, просто используя команду pip .
Алгоритм нахождения простых чисел
Дело было давно, в университете, когда мы начали изучать язык программирования Pascal и домашним заданием стало создание алгоритма нахождения простых чисел.
Алгоритм был придуман и тутже реализован на изучаемом языке. Программа запрашивала у пользователя число N и искала все простые числа до N включительно. После первого успешного теста сразу же возникло непреодолимое желание ввести N = «много». Программа работала, но не так быстро как хотелось бы. Естественно, дело было в многочисленных проверках (порядка N*N/2), поэтому пришлось избавиться от лишних. В итоге получилось 5 похожих алгоритмов каждый из которых работал быстре предыдущего. Недавно захотелось их вспомнить и реализовать, но на этот раз на Python.
Итак, поехали. Первый алгоритм, ударивший в студенческую голову, продемонстрирован в Листинге 1.
# Листинг 1 # вводим N n = input(«n python»># Листинг 2 n = input(«n python»># Листинг 3 n = input(«n python»># Листинг 4 from math import sqrt n = input(«n python»># Листинг 5 from math import sqrt n = input(«n python»># Листинг 6 from math import sqrt n = input(«n python»># Листинг 7 n = input(«n python»># Листинг 8 n = input(«n tm-article-presenter__meta»>
Решето Эратосфена в Python
Статьи
Введение
В ходе статьи используя алгоритм “Решето Эратосфена” найдём все простые числа до заданного числа N в Python.
Решето Эратосфена – это алгоритм нахождения всех простых чисел в диапазоне от 0, до заданного числа N.
Написание кода
Для начала дадим пользователю возможность ввода числа верхней границы диапазона:
Используя генератор заполним список значениями от одного, до заданного числа N:
Так как единица не является простым числом, заменим её на ноль:
Создадим переменную i равную двум, чтобы начать сразу с третьего элемента:
Создадим цикл, который не закончится, пока i <= n. Внутри цикла зададим условие, что если значение ячейки ранее не было обнулено, то в ней хранится простое число. Первое кратное ему число будет больше в два раза:
Далее внутри условия создадим ещё один цикл while, который не закончится, пока j <= n. Мы выявили, что данное число является составным, поэтому заменяем его нулём. Прибавляем i к j:
Преобразуем список в множество, после чего удалим все нули и выведем его:
Заключение
В ходе статьи мы с Вами научились использовать алгоритм “Решето Эратосфена” для нахождения всех простых чисел в заданном диапазоне и написали код на Python. Надеюсь Вам понравилась статья, желаю удачи и успехов! ��