Рекурсія #8

Повернутись

-= (0|8) =-

Далі

Використаємо формулу ...

Задача #2862 Кількість дільників

Спочатку розкладемо 720 на множники:

720 = 2⁴ · 3² · 5

Отже, у нас є

4 + 1 = 5 варіантів для двійки (дільник містить від 0 до 4 двійок включно),
2 + 1 = 3 варіант для трійки та
1 + 1 = 2 варіанти для п'ятірки.

Отже, у числа 720 5 · 3 · 2 = 30 дільників.

Формула Ейлера для знаходження кількості дільників натурального числа.

(а може й не Ейлера )

https://uk.wikipedia.org/wiki/Основна_теорема_арифметики

Кількість дільниківЗнайти кількість дільників числа .

Код: рекурсія

# РЕКУРСІЯ

def dil(n, x, d):

if n == 1: # Базовий випадок

return x

else: # Рекурсивний випадок

k = 0

while n % d == 0:

k = k + 1

n = n // d

return dil(n, x*(k + 1), d + 1)

n=int(input())

print(dil (n, 1, 2))

Код: рекурсія з декоратором

# РЕКУРСІЯ з ДЕКОРАТОРОМ

def cache(f):

cache = {}

stack = []

def wrap(*args):

if args not in cache:

if stack:

stack.append(args)

cache[args] = f(*args)

stack.pop()

else:

stack.append(args)

while stack:

args = stack[-1]

if args in cache:

stack.pop()

else:

try:

r = f(*args)

except RecursionError:

pass

else:

cache[args] = r

return cache[args]

return wrap

@cache

def f(n, x, d):

if n == 1: # Базовий випадок

return x

else: # Рекурсивний випадок

k = 0

while n % d == 0:

k = k + 1

n = n // d

return f(n, x*(k + 1), d + 1)

n=int(input())

print(f (n, 1, 2))

Де ж помилка?

if n == 1:

RecursionError: maximum recursion depth exceeded in comparison

997 - просте число!

https://ua.onlinemschool.com/math/library/numbers/prime-number/

Використаємо інтерацію

Олександр Сидоренко. З чого почати програмувати? Полтава 2023

Задача #42 Кількість дільників

Як я можу покращити цей код, щоб знайти кількість дільників?

1 та n - очевидні дільники
використати інформацію про те, що дільники ходять парочками

Код: цикл

# ЦИКЛ

n=int(input())

k = 0

for i in range(1, n + 1):

if n % i == 0:

k += 1

print (k)

Код: цикл #1

# ЦИКЛ (покращення 1 - очевидні дільники)

n=int(input())

k = 2

for i in range(2, n):

if n % i == 0:

k += 1

print (k)

Код: цикл #2

# ЦИКЛ (покращення 2 - дільники ходять парами)

import math

n=int(input())

k = 2

for i in range(2, int(math.sqrt(n)) + 1):

if n % i == 0:

if i * i == n:

k += 1

else:

k += 2

print (k)

Повернутись

-= (0|8) =-

Далі