Найти все простые делители числа питон

Делители числа

Делитель — это число, на которое нацело делится делимое. У делимого может быть один или несколько делителей, найти их все можно с помощью простого алгоритма, который без проблем реализуется на Python 3.

Нахождение делителей числа

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

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

Алгоритм нахождения очень простой. В цикле перебираются значения от делимого минус единица до двух включительно. Если делимое нацело делится на текущее значение, то оно является делителем.

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

numb = int(input("Введите целое число: ")) print("Результат:", end = " ") for i in range(numb - 1, 1, -1): if (numb % i == 0): print(i, end = " ")

Например, пользователь ввёл число 625. Программа начинает цикл со значения 624, в цикле проверяется, делится ли нацело 625 на 624, затем цикл переходит на следующую итерацию и работает уже с числом 623 и так до двух. Таким образом, вывод программы будет следующим:

Введите целое число: 625 Результат: 125 25 5

Простые делители числа

Простой делитель — это делитель, который делится только на единицу и самого себя. Для нахождения простых делителей с помощью Python нужно немного модернизировать программу, добавив в неё дополнительный цикл for и переменную счётчик.

Программа построена по следующему алгоритму:

1. Обнулить счётчик.
2. В цикле искать делители.
3. Если найден, искать во вложенном цикле его делители. Это для того, чтобы определить: является ли он простым.
4. Если найден, увеличить счётчик.
5. Если счётчик равен нулю, то число простое и надо вывести значение делителя в консоль.
6. Перейти на следующую итерацию внешнего цикла.

Цикл теперь выглядит так:

numb = int(input("Введите целое число: ")) print("Простые:", end = " ") for i in range(numb - 1, 1, -1): is_simple = 0 # Счётчик if (numb % i == 0): for j in range(i - 1, 1, -1): if (i % j == 0): is_simple = is_simple + 1 # Увеличиваем, если находим делитель if (is_simple == 0): # Если делителей не было найдено, выводим print(i, end = " ")

Понятно, что если значение счётчика больше нуля — то число точно не простое. Можно оптимизировать немного код и сразу завершать вложенный цикл после увеличения счётчика. Для этого можно воспользоваться оператором break в условном операторе, находящемся во вложенном цикле.

Результат работы программы:

Введите целое число: 63 Простые: 7 3

Делители расположены в порядке убывания. И если надо вывести только самый большой простой делитель с помощью Python, то можно после того, как выведется первое число, воспользоваться оператором break для выхода из цикла.

Сумма делителей

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

Код программы:

numb = int(input("Введите целое число: ")) sum_of_dividers = 0 for i in range(numb - 1, 1, -1): if (numb % i == 0): sum_of_dividers += i print("Сумма:", sum_of_dividers)

Результат выполнения кода:

Введите целое число: 63 Сумма: 40

Количество делителей

Этот вариант программы также лишь незначительно отличается от изначального. Для подсчёта делителей нужно ввести переменную-счётчик, к которой будет прибавляться единица каждый раз, когда условие « numb % i == 0 » будет выполняться.

numb = int(input("Введите целое число: ")) count_of_dividers = 0 for i in range(numb - 1, 1, -1): if (numb % i == 0): count_of_dividers += 1 print("Количество равно:", count_of_dividers)

Результаты выполнения программы:

Введите целое число: 63 Количество равно: 4

Максимальный и минимальный делитель

Для нахождения минимального и максимального делителя в код на Python нужно добавить две переменные: min_divider и max_divider . В цикле делитель будет сравниваться со значением этих переменных и, если необходимо, записываться в них.

Код программы:

numb = int(input("Введите целое число: ")) min_divider = numb max_divider = 1 for i in range(numb - 1, 1, -1): if (numb % i == 0): if (min_divider > i): min_divider = i if (max_divider < i): max_divider = i print("Минимальный равен:", min_divider) print("Максимальный равен:", max_divider)

Результат выполнения:

Введите целое число: 63 Минимальный равен: 3 Максимальный равен: 21

Нахождение наименьшего и наибольшего делителя, подсчёт суммы делителей и их количества можно объединить в одну программу на Python. Это не должно вызвать каких-либо проблем или конфликтов, потому что программа работает с 4 независимыми переменными.

Источник

Нахождение делителей числа с помощью 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! выглядит следующим образом:
 
Вычисление такой факторизации относительно эффективно, особенно для факториалов, так как, поскольку все простые множители очень малы, вам не нужно делать много делений.
 
В теории чисел есть утверждение, называемое основной теоремой арифметики, которое гласит, что простые факторизации (разложения) уникальны: для любого числа 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!
 
Такая реализация очень эффективна, особенно когда у вас много маленьких простых множителей, как в случае с факториалами, с которыми я работал. Я не знаю, насколько хорошо она покажет себя в общем случае, и, если вы занимаетесь серьезными научными вычислениями, я уверен, что вы легко найдете уже реализованные и оптимизированные алгоритмы для такого рода вещей.
 
Источник
 
Как найти простые делители для числа?
 
Простые делители числа
Здравствуйте, помогите, пожалуйста, найти все простые делители от числа 4679000 до 5000000 Там.
 
 
 Простые числа и делители
Дано натуральное число P. Вывести на экран все простые числа, не превосходящие P. Посчитать их.
 
Получить все делители числа q взаимно простые с p
Даны натуральные числа p и q. Получить все делители числа q взаимно просты с p.
 
Целые числа (делители, простые, НОД, НОК, цифры)
Даны натуральные числа a и b, обозначающие соответственно числитель и знаменатель дроби. Сократить.
 
 
 
Сообщение было отмечено Catstail как решение
 
Решение
 
1 2 3 4 5 6 7 8 9 10 11 12 13 14
 
def delit(a) : res = [] i = 2 while i * i  a + 1 : if a % i == 0 : res.append(i) while a % i == 0 : a //= i i += 1 if a != 1 : res.append(a) return res print(delit(int(input())))
 
 
 
Сообщение было отмечено Catstail как решение
 
Решение
 
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
 
def delit(a) : res = [] i = 2 # цикл до квадратного корня из "а" # больше этого без остатка не делится, если только . # (об этом ниже) while i * i  a + 1 : # если при делении остаток = 0, то добавляем "i" в список if a % i == 0 : res.append(i) # теперь делим исходное число на "i", пока не появится остаток while a % i == 0 : a //= i # берем следующее "i" i += 1 # если в конце "а" не равно единице, то значит остался один(!) # делитель, больший кв. корня из исходного "а" # добавляем в список if a != 1 : res.append(a) return res print(delit(int(input())))
 
Не подскажите, почему ваш код не работает с числом 600851475143? 
Быстро выдаёт ответ - 1471. 
При обычном переборе выдаёт ПРАВИЛЬНЫЙ ответ - 6857, но это раз в 20 дольше получается.
 
Соответственно задача была -
 
Largest prime factor 
The prime factors of 13195 are 5, 7, 13 and 29.
 
What is the largest prime factor of the number 600851475143 ?
 
Добавлено через 17 минут 
Разобрался, удалить не успел (( 
 
func largestPrimeFactor(_ num: Int) < var num = num var res = 0 var i = 2 var largestPrime = 0 while i * i < num + 1 < if num % i == 0 && i >res < res = i largestPrime = num / res >while num % i == 0 < num /= i >i += 1 > print(largestPrime) > largestPrimeFactor(600851475143) largestPrimeFactor(13195)
 
Источник