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 you have read our privacy policy.

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