проверка всех делителей числа на python

Question

Есть такая задача - определить, делится ли первое число 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))

Answer 1

Если вы уже получили все простые делители для обоих чисел, то дальше можно воспользоваться методом 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

Answer 2

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

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

Answer 3

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

вычисляем НОД(a, b)
итерационно вычисляем НОД(b / НОД, НОД)
если в конце НОД будет равен 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 строчку меньше :)

БЛОГ НА HUSL

проверка всех делителей числа на python

Ответы (3 шт):