1 Востаннє редагувалося mamkin haker (18.10.2021 18:16:36)

Тема: НЕ цікава задачка

Задачка:
Скільки є чисел на проміжку від 1 до 180, які не взаємно прості з 30?
(код нище не працює)

def get_numbers(k = 0, number = 30) -> list:
    k_numbers = []

    for i in range(1, number + 1):
        if (number % i == 0):
            k_numbers.append(i)

    return k_numbers

def check_numbers(k_numbers, number = 180) -> int:
    k = 0

    for i in range(1, number + 1):
        for j in k_numbers:
            if (i % j != 0):
                k += 1
                break
    
    return k

def main() -> int:
    k_numbers = get_numbers()
    k = check_numbers(k_numbers)
    print(k)
    return 0

if __name__ == "__main__":
    main()
Подякували: P.Y.1

2 Востаннє редагувалося mamkin haker (18.10.2021 17:43:04)

Re: НЕ цікава задачка

k = 0
for i in range(1, 181):
    if (i % 2 == 0 or i % 3 == 0 or i % 5 == 0):k += 1
print(k)

аналогічно рахує...

3 Востаннє редагувалося mamkin haker (18.10.2021 18:10:46)

Re: НЕ цікава задачка

ніби правильно

k = 0
for i in range(1, 181):
    if not(i % 2 == 0 or i % 3 == 0 or i % 5 == 0):k += 1
print(180 - k)

*********** , [18.10.21 18:49]
Так, 132

4

Re: НЕ цікава задачка

Це ж, скорочено:

print(180 - sum(1 for i in range(1, 181) if not(i % 2 == 0 or i % 3 == 0 or i % 5 == 0)))

По-перше, обернемо умову і позбудемося віднімання:

print(sum(1 for i in range(1, 181) if i % 2 == 0 or i % 3 == 0 or i % 5 == 0))

умову можна перетворити на, скажімо,

if 0 in [i%2, i%3, i%5]

або ж

if any(i % divisor == 0 for divisor in (2, 3, 5))

Останнє вже досить загальне, щоб можна було робити функцію:

def count_non_coprimes(divisors, limit):
    return sum(1 for i in range(1,limit+1) if any(i%divisor == 0 for divisor in divisors))

Для любителів заплутування через спрощення можна скористатися тим, що int(True)==1, а int(False)==0:

def count_non_coprimes(divisors, limit):
    return return sum(any(i%divisor == 0 for divisor in divisors) for i in range(1,limit+1))

Однак початкова задача була не зі списком дільників, а з числом. Ну що ж, скористаємося math.gcd:

def count_non_coprimes(number, limit):
    return sum(1 for i in range(1,limit+1) if math.gcd(number,i)>1)

Перевіряємо:

>>> count_non_coprimes(30,180)
132
Подякували: mamkin haker, leofun01, P.Y., dot4

5 Востаннє редагувалося mamkin haker (18.10.2021 21:26:47)

Re: НЕ цікава задачка

upd важко для розуміння -_-

6

Re: НЕ цікава задачка

mamkin haker написав:

Задачка:
Скільки є чисел на проміжку від 1 до 180, які не взаємно прості з 30?

koala написав:

початкова задача була не зі списком дільників, а з числом.

Початкова задача була не зі списком.
Результатом має бути число, і його можна знайти за час незалежний від розміру range (O(1)).

7

Re: НЕ цікава задачка

Зате залежний від розміру числа (O(n)).

Подякували: leofun011

8

Re: НЕ цікава задачка

koala написав:

Зате залежний від розміру числа (O(n)).

Не зрозумів. Того що 30 ?

9

Re: НЕ цікава задачка

Так

Подякували: leofun011

10 Востаннє редагувалося mamkin haker (23.10.2021 19:37:42)

Re: НЕ цікава задачка

ой, нетуди :D