Как найти простые делители для числа?
Простые делители числа
Здравствуйте, помогите, пожалуйста, найти все простые делители от числа 4679000 до 5000000 Там.
Простые числа и делители
Дано натуральное число P. Вывести на экран все простые числа, не превосходящие P. Посчитать их.
Получить все делители числа q взаимно простые с p
Даны натуральные числа p и q. Получить все делители числа q взаимно просты с p.
Целые числа (делители, простые, НОД, НОК, цифры)
Даны натуральные числа a и b, обозначающие соответственно числитель и знаменатель дроби. Сократить.
7279 / 4102 / 1794
Регистрация: 27.03.2020
Сообщений: 6,926
Сообщение было отмечено Catstail как решение
Решение
Daniil4k, Да. уж.
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())))
Регистрация: 25.09.2019
Сообщений: 208
Gdez, Спасибо. А можешь обьяснить что ты сделал?
7279 / 4102 / 1794
Регистрация: 27.03.2020
Сообщений: 6,926
Сообщение было отмечено Catstail как решение
Решение
Daniil4k,
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())))
Регистрация: 20.09.2015
Сообщений: 14
Не подскажите, почему ваш код не работает с числом 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)
Как найти делители числа с помощью функции в Python?
Функция для нахождения делителей целого положительного числа:
def get_divisors(number): # Чтобы делители в списке не повторялись, собираем их в множество. result = 1, number> # Перебираем диапазон до number // 2, потому что единственный делитель # больше половины числа - это само число, его мы уже включили в результат. # Чтобы половина тоже вошла в диапазон, добавляем к ней 1. for divisor in range(2, number // 2 + 1): if number % divisor == 0: result.add(divisor) # функция sorted() сортирует делители по возрастанию и возвращает результат в виде списка return sorted(result) get_divisors(1) # [1] get_divisors(2) # [1, 2] get_divisors(11) # [1, 11] get_divisors(33) # [1, 3, 11, 33] get_divisors(64) # [1, 2, 4, 8, 16, 32, 64] Проверка простоты числа перебором делителей
Простые числа — это натуральные числа больше единицы, которые делятся нацело только на единицу и на себя. Например, число 3 простое, так как нацело делится только на 1 и 3. Число 4 сложное, так как нацело делится не только на 1 и 4, но также на число 2.
Алгоритм перебора делителей заключается в последовательном делении заданного натурального числа на все целые числа, начиная с двойки и заканчивая значением меньшим или равным квадратному корню из тестируемого числа. Таким образом, в данном алгоритме используется цикл, счетчик итераций которого последовательно принимает значения ряда натуральных чисел от 2 до корня из исследуемого числа.
Перебор делителей применяется в том числе для определения, является ли натуральное число простым, или оно является сложным, то есть составным. Касаемо данной задачи, если хотя бы один делитель делит исследуемое число без остатка, то оно является составным. Если ни одного такого делителя не находится, то число признается простым.
from math import sqrt n = int(input()) prime = True i = 2 while i sqrt(n): if n % i == 0: prime = False break i += 1 if prime: print("Простое число") else: print("Составное число")
В программе мы сначала предполагаем, что введенное число n является простым, и поэтому присваиваем переменной prime значение True . Далее в цикле перебираются делители (переменная i ) от 2-х до квадратного корня из числа n . Как только встречается первый делитель, на который n делится без остатка, меняем значение prime на False и прерываем работу цикла, так как дальнейшее тестирование числа на простоту смысла не имеет.
Если после выполнения цикла prime осталась истиной, сработает ветка if условного оператора. В случае False , поток выполнения заходит в ветку else .
Если знать о такой особенности циклов в Python как возможность иметь ветку else , то код можно упростить, избавившись от переменной prime и ее проверки условным оператором после завершения работы цикла.
from math import sqrt n = int(input()) i = 2 while i sqrt(n): if n % i == 0: print("Составное число") break i += 1 else: print("Простое число")
Ветка else при циклах (как while , так и for ) срабатывает, если в основном теле цикла не происходило прерывания с помощью break . Если break сработал, то тело else выполняться не будет. При использовании таких конструкций также следует помнить, что если условие в заголовке цикла сразу возвращает ложь (то есть тело цикла не должно выполняться ни разу), код тела else все-равно будет выполнен.
Программы выше будут определять числа 0 и 1 как простые. Это неправильно. Данные числа не являются ни простыми, ни сложными. Для проверки ввода пользователя, можно воспользоваться условным оператором или зациклить запрос числа, пока не будет введено корректное значение:
n = 0 while n 2: n = int(input())
Рассмотрим функцию, которая определяет, является ли число простым:
from math import sqrt def is_prime(n): i = 2 while i sqrt(n): if n % i == 0: return False i += 1 if n > 1: return True a = int(input()) if is_prime(a): print("Простое число") else: print("Число НЕ является простым")
Здесь нет необходимости в прерывании работы цикла с помощью break , так как оператор return выполняет выход из тела всей функции.
Если цикл полностью отработал, выполнится выражение return True , находящееся ниже цикла. Оно помещено в тело условного оператора, чтобы исключить возврат «истины», когда в функцию передаются числа 0 или 1. В этом случае функция вернет объект None .
Программа не защищена от ввода отрицательного числа. При этом будет генерироваться ошибка на этапе извлечения квадратного корня.
Нарисуем блок-схему тестирования числа на простоту (без дополнительных проверок и оператора break ):
from math import sqrt n = int(input()) prime = True i = 2 while i sqrt(n) and prime is True: if n % i == 0: prime = False i += 1 if prime: print("Простое число") else: print("Составное число")
—>
X Скрыть Наверх
Решение задач на Python
Объясните алгоритм нахождения простых делителей числа [закрыт]
Закрыт. Этот вопрос необходимо уточнить или дополнить подробностями. Ответы на него в данный момент не принимаются.
Хотите улучшить этот вопрос? Добавьте больше подробностей и уточните проблему, отредактировав это сообщение.
Закрыт 3 года назад .
Можете объяснить алгоритм данного кода. Данный код находит простые делители числа.
def simpleDividers(n): answer = [] d = 2 while d * d 1: answer.append(n) return answer Отслеживать
171 2 2 серебряных знака 23 23 бронзовых знака
задан 25 июн 2020 в 15:54
Krasava666777 Krasava666777
1 1 1 серебряный знак 1 1 бронзовый знак
А что тут говорить. не самый эффективный способ разложения числа на простые множители.
25 июн 2020 в 15:57
1 ответ 1
Сортировка: Сброс на вариант по умолчанию
def simpleDividers(n): answer = [] # пустой список d = 2 # начальное значение проверяемого делителя while d * d 1: # если в итоге n > 1 answer.append(n) # добавляем в ответ ещё этот n return answer # возвращаем Отслеживать
ответ дан 25 июн 2020 в 15:57
171 2 2 серебряных знака 23 23 бронзовых знака
А как именно действует цикл while? Непонятно почему именно такой алглоритмм
25 июн 2020 в 16:28
@Krasava666777 что именно непонятно? Каждая строчка же прокомментирована. Вот одно из многих описаний алгоритма ru.wikipedia.org/wiki/Перебор_делителей
25 июн 2020 в 16:31
- python
- алгоритм
-
Важное на Мете
Похожие
Дизайн сайта / логотип © 2023 Stack Exchange Inc; пользовательские материалы лицензированы в соответствии с CC BY-SA . rev 2023.11.15.1019
Нажимая «Принять все файлы cookie» вы соглашаетесь, что Stack Exchange может хранить файлы cookie на вашем устройстве и раскрывать информацию в соответствии с нашей Политикой в отношении файлов cookie.