Оптимизировать алгоритм поиска кратных чисел

Question

Надо найти все числа кратные хотя бы одному из 2-х чисел(напр. 7 и 19) и вернуть список кратных чисел. Требование вывести именно список кратных чисел, поэтому тут никак не схитрить. Я решил оптимизировать код и не использовать простой перебор всех чисел. Первая мысля - это взять наименьшее число и прибавлять каждый проход это же число(напр. кратность 7 т.е. 7 а дальше 14, 21 и т д. и аналогично для второго числа). Для эксперимента я замерил время моего "эффективного" алгоритма и время простого перебора - выхлоп не очень, на отрезке от 0 до 100 млн выигрыш 1-3 секунд(на отрезках много меньше выигрыш вообще в пределах погрешности). Из этого два вопроса: 1) есть ли более эффективный алгоритм для поиска 2(а может и более) кратных чисел? 2) влияет конкретно в python тот факт, что я +- 10 млн чисел запихал в память влияет на производительность?

предложенный алгоритм

def sol (count, num1, num2):
res = []
working = True
flag1 = True
flag2 = True

while(working):
    if num1 <= count:
        res.append(num1)
        num1 += 3
    else:
        flag1 = False
        
    if num2 <= count:
        res.append(num2)
        num2 += 5
    else:
        flag2 = False
        
    if not(flag1 or flag2):
        working = False
    
    
res = list(set(res))
return res

как я сделал простой перебор

def sec_sol(count, num1, num2):
res = []
for i in range(count + 1):
    if i % num1 == 0 or i % num2 == 0:
        res.append(i)
        
res = list(set(res))
return res

и вот замеры по времени с модулем time()

11.5572 - первый "эффективный" алгоритм
12.6264 - простой перебор

Answer 1

А не хотите найти НОК и дальше не мучиться?...

def gcd(m,n):
    while m != 0 and n != 0:
        if m < n:
            n %= m
        else:
            m %= n
    return m+n

def lcm(m,n):
    return (m//gcd(m,n))*n

def sol (count, num1, num2):
    res = []
    l = lcm(num1,num2)
    for i in range(1,count+1):
        res.append(l*i)
    return res

Да, ваше

числа кратные заданным 2м числам

я рассматриваю как кратные одновременно обоим заданным числам. Если это не так, перепишите условие как кратные хотя бы одному из двух заданных чисел.

Update

Тогда примерно так:

def sol (num1, num2, count):
    res = []
    if num1 > num2:
        tmp = num1
        num1 = num2
        num2 = tmp

    k = 0
    m1 = num1
    m2 = num2
    while 1:
        if m1 < m2:
            res.append(m1)
            m1 += num1
        elif m1 > m2:
            res.append(m2)
            m2 += num2
        else:
            res.append(m2)
            m2 += num2
            m1 += num1
        if m1 > count or m2 > count:
            break
    return res

Answer 2

Что-то такое будет работать быстрее:

def multiples(nums, upper_limit):
    s = set()
    for n in nums:
        s.update(range(n, upper_limit, n))
    return sorted(s)


print(len(multiples((7, 19), 100_000_000)))

$ time python multiples.py
18796992

real  0m2.268s
user  0m1.776s
sys   0m0.484s

P.S. В вопросе, кажется, мало смысла. Расскажите зачем вам это нужно.

БЛОГ НА HUSL

Оптимизировать алгоритм поиска кратных чисел

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