2

Есть такая задача - определить, делится ли первое число a на все простые множители второго числа b. Например: solve (15,12) = False, потому что 15 не делится на все простые множители 12 (включая 2). Я дошел до ммомента, когда знаю кто делители a и b.

Но как сделать проверку для всех элементов сразу а не по одному как у меня? У меня выходит True и False на каждый элемент, а должно только один раз или то или другое. Спасибо

def solve(a, b):
    for i in range(1,b+1):
        if b % i == 0:
            b_div = set([i]) #  1 3 5 15
            if a % i == 0:
                a_div = set([i]) # 1 2 3 4 6 12

    if b_div.issubset(a_div):
        return True
    else:
        return False
print(solve(15,12))
1
  • В b_div не бывает больше одного элемента. Тут ошибка. 11 дек 2021 в 18:13

3 ответа 3

3

если имеется в виду, что просто на простые делители числа b, а не на их произведение, то без поиска простых множителей можно сделать следующее

  1. вычисляем НОД(a, b)

  2. итерационно вычисляем НОД(b / НОД, НОД)

  3. если в конце НОД будет равен 1, и b будет равно 1 - условие выполнено

код:

import math

a = 15
b = 12

gcd = math.gcd(a, b)
b //= gcd

while gcd != 1:
    gcd = math.gcd(b, gcd)
    b //= gcd

print("SUCCESS" if b == 1 else "FALSE")

быстро, дешево и сердито :)

P.S. подумал, что до цикла b //= gcd можно и не делать было - просто в цикле на 1 шаг будет больше, зато кода на 1 строчку меньше :)

4
  • спасиб Вам! Можете посоветовать как прокачать мозги на решение задач. В какую сторону можно посмотреть еще, кроме codewars. Знаю про hackerrank & leetcode, первая вроде тоже хороший ресурс, а 2 чисто для интервью. Спасибо 11 дек 2021 в 18:36
  • Прокачаться на решении задач - простой делайте задачи :) можно для себя и полезные для вас, чтобы изучать особенности питона на мелких задачах - можно ставить перед собой цели типа 1) сделать самый быстрый код 2) сделать самый короткий код и т.д. В любом случае не надо делать что-то ради самоцели. Вот честно признают из всего вами перечисленного ни о чем не слышал :(
    – Zhihar
    11 дек 2021 в 18:42
  • @Zhihtar, спасибо большое еще раз! эту задачку взял отсюда, если будет интересно: codewars.com/kata/59ec2d112332430ce9000005 11 дек 2021 в 18:43
  • Очень красивое решение. 11 дек 2021 в 18:56
2

Если вы уже получили все простые делители для обоих чисел, то дальше можно воспользоваться методом set.issubset() (или перегруженным для множеств оператором <=).

Пример:

In [208]: a_div = set([3, 5])

In [209]: b_div = set([2, 3])

In [210]: res = a_div <= b_div

In [211]: res
Out[211]: False

пример использования метода set.issubset():

In [212]: {2,3}.issubset([2,3,5,7])
Out[212]: True
4
  • сделал так, но все равно не принимает. Подскажите пожалуйста в чем дело. Обновил код. Спасибо 11 дек 2021 в 17:54
  • @user9085541, эта проверка должна быть после того, как вы получили все простые делители для обоих чисел. Не понимаю почему вы поместили ее в цикл... 11 дек 2021 в 17:56
  • еще раз обновил, но тоже самое 11 дек 2021 в 18:03
  • @user9085541, а вы проверили после работы цикла - правильные ли у вас делители в переменных a_div, b_div ? В вопросе вы утверждали, что с делителями у вас все OK. 11 дек 2021 в 18:04
1

Вам надо подкорректировать последовательность. Вот пример как получилось у меня:

def solve(a,b):
    is_prime = lambda n,i=2: is_prime(n,i+1) if i*i<=n and n%i else i*i>n
    for i in range(2,b+1):
        if b % i == 0 and is_prime(i) and a % i:
            return False
    return True

В цикле проверяем в первом условии делитель, во втором его простоту и в третьем делимость первого числа. Если второе или третье условие не выполняются возвращаем False.

UPD

для решения на codewars можно попробовать так:

from gmpy2 import is_prime

def solve(a,b):
    for i in range(2,b+1):
        if b % i == 0 and is_prime(i) and a % i:
            return False
    return True
8
  • он мне ошибку дал; RecursionError: maximum recursion depth exceeded in comparison 11 дек 2021 в 18:21
  • @user9085541 какие были числа на входе?
    – SergFSM
    11 дек 2021 в 18:23
  • задача с сайта codewars: там такие вводятся 2,256 11 дек 2021 в 18:25
  • @user9085541 на codewars ограничение глубины рекурсии. добавил в ответ код специально для codewars
    – SergFSM
    11 дек 2021 в 18:30
  • к сожалению без изменений 11 дек 2021 в 18:33

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.