Питон как в списке найти простые числа

и не париться с абсолютным значением, но иногда приходилось считать и отрицательные простыми числами (при использовании основной теоремы арифметики), вернее не считать, а использовать отрицательные как простые при разложении

хотя для не целых чисел я бы все таки выбрасывал исключение - логически наверное более правильно это

P.S.

кстати для простого числа есть и другое определение для которого код будет вот таким коротким, без проверки на 1 и отрицательные числа:

return len([i for i in range(1, n + 1) if n % i == 0]) == 2 

Вывести все простые числа в диапазоне Python – пошаговый алгоритм

Простое число — это натуральное число, которое больше 1 и не имеет положительного делителя, кроме 1 и самого себя, например 2, 3, 5, 7, 11, 13 и так далее.

Пользователю даются два целых числа, нижнее значение и верхнее значение. Задача состоит в том, чтобы написать программу Python для вывода всех простых чисел в заданном интервале (или диапазоне).

Чтобы напечатать все простые числа в заданном интервале, пользователь должен выполнить следующие шаги:

• Шаг 1: Переберите все элементы в заданном диапазоне.
• Шаг 2: Проверьте для каждого числа, есть ли у него какой-либо множитель между 1 и самим собой.
• Шаг 3: Если да, то число не простое, и оно перейдет к следующему числу.
• Шаг 4: Если нет, то это простое число, и программа распечатает его и проверит следующее число.
• Шаг 5: Цикл прервется, когда будет достигнуто верхнее значение.

Пример: код Python для печати простого числа в заданном интервале.

# First, we will take the input: lower_value = int(input("Please, Enter the Lowest Range Value: ")) upper_value = int(input("Please, Enter the Upper Range Value: ")) print("The Prime Numbers in the range are: ") for number in range(lower_value, upper_value + 1): if number > 1: for i in range(2, number): if(number % i) == 0: break else: print(number)

Please, Enter the Lowest Range Value: 14 Please, Enter the Upper Range Value: 97 The Prime Numbers in the range are: 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Заключение

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

Алгоритм нахождения простых чисел

Дело было давно, в университете, когда мы начали изучать язык программирования 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, каковы все его делители?

Делитель, также известный как фактор или множитель, — это такое целое число m, на которое n делится без остатка. Например, делителями числа 12 являются 1, 2, 3, 4, 6 и 12.

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

Простейший подход

Если мы хотим найти все числа, которые делят n без остатка, мы можем просто перебрать числа от 1 до n:

 
 
def get_all_divisors_brute(n): for i in range(1, int(n / 2) + 1): if n % i == 0: yield i yield n
На деле нам нужно дойти только до n/2, потому что все, что больше этого значения, гарантировано не может быть делителем n — если вы разделите n на что-то большее, чем n/2, результат не будет целым числом.
Этот код очень прост, и для малых значений n он работает достаточно хорошо, но он довольно неэффективен и медлителен в других случаях. По мере увеличения n время выполнения линейно увеличивается. Можем ли мы сделать лучше?
Факторизация
В моем проекте я работал в основном с факториалами. Факториал числа n, обозначаемый n! — это произведение всех целых чисел от 1 до n включительно. Например:
8! = 8 × 7 × 6 × 5 × 4 × 3 × 2 × 1
Поскольку факториалы состоят преимущественно из небольших множителей, я решил попробовать получить список делителей, определив сначала наименьшие из них. В частности, я искал простые множители, то есть те, которые также являются простыми числами. (Простое число — это число, единственными делителями которого являются оно само и 1. Например, 2, 3 и 5 являются простыми, а 4 и 6 — нет).
Вот функция, которая находит простые делители числа n:
 
 
def get_prime_divisors(n): i = 2 while i * i 1: yield n
Это похоже на предыдущую функцию, использующую перебор делителей: мы продолжаем пробовать множители, и если находим подходящий, то делим на него. В противном случае мы проверяем следующее число. Это довольно стандартный подход к поиску простых множителей.
Теперь мы можем использовать этот метод для получения факторизации числа, то есть для его записи в виде произведения простых чисел. Например, факторизация числа 8! выглядит следующим образом:
8! = 2^7 × 3^2 × 5 × 7
Вычисление такой факторизации относительно эффективно, особенно для факториалов, так как, поскольку все простые множители очень малы, вам не нужно делать много делений.
В теории чисел есть утверждение, называемое основной теоремой арифметики, которое гласит, что простые факторизации (разложения) уникальны: для любого числа n существует только один способ представить его в виде произведения простых множителей. (Я не буду приводить здесь доказательство, но вы можете найти его в Википедии).
Это дает нам способ находить делители путем перебора всех комбинаций простых множителей. Простые множители любого m делителя числа n должны входить в подмножество простых множителей n, иначе m не делило бы число n.
Переход от факторизации к делителям
Для начала разложим исходное число на простые множители с указанием «кратности», то есть мы должны получить список всех множителей и количество раз, которое каждый из них встречается в факторизации:
 
 
import collections def get_all_divisors(n): primes = get_prime_divisors(n) primes_counted = collections.Counter(primes) .
Затем, давайте продолжим и возведем каждое простое число во все степени, которые могут появиться в возможном делителе n.
 
 
def get_all_divisors(n): . divisors_exponentiated = [ [div ** i for i in range(count + 1)] for div, count in primes_counted.items() ]
Например, для 8! представленный код выдаст нам следующее:
 
 
[ [1, 2, 4, 8, 16, 32, 64, 128], // 2^0, 2^1, . 2^7 [1, 3, 9], // 3^0, 3^1, 3^2 [1, 5], [1, 7], ]
Затем, чтобы получить делители, мы можем использовать довольно удобную функцию itertools.product, которая принимает на вход итерабельные объекты и возвращает все возможные упорядоченные комбинации их элементов. В нашем случае она выбирает по одному числу из каждого списка с возведениями в степень, а затем, перемножая их вместе, мы получаем очередной делитель n.
 
 
import itertools def calc_product(iterable): acc = 1 for i in iterable: acc *= i return acc def get_all_divisors(n): . for prime_exp_combination in itertools.product(*divisors_exponentiated): yield calc_product(prime_exp_combination)
Таким образом, мы находим все делители n (хотя, в отличие от предыдущих функций, они не отсортированы).
Собираем все вместе
Сложив все это, мы получим следующую функцию для вычисления делителей n:
 
 
import collections import itertools def get_prime_divisors(n): i = 2 while i * i 1: yield n def calc_product(iterable): acc = 1 for i in iterable: acc *= i return acc def get_all_divisors(n): primes = get_prime_divisors(n) primes_counted = collections.Counter(primes) divisors_exponentiated = [ [div ** i for i in range(count + 1)] for div, count in primes_counted.items() ] for prime_exp_combination in itertools.product(*divisors_exponentiated): yield calc_product(prime_exp_combination) print(list(get_all_divisors(40320))) # 8!
Такая реализация очень эффективна, особенно когда у вас много маленьких простых множителей, как в случае с факториалами, с которыми я работал. Я не знаю, насколько хорошо она покажет себя в общем случае, и, если вы занимаетесь серьезными научными вычислениями, я уверен, что вы легко найдете уже реализованные и оптимизированные алгоритмы для такого рода вещей.
Читать:
Что такое nano cell в телевизорах lg