Практическая задача по Python: все делители числа
Разбор задачи о делителях числа
Условие:
Пользователь вводит целое положительное число. Программа выводит все его делители (включая 1 и само число).
Как реализовать простой перебор делителей?
Самый очевидный способ - проверить все числа от 1 до n. Если n делится на i без остатка, то i - делитель.
n = int(input("Введите число: "))
for i in range(1, n + 1):
if n % i == 0:
print(i)задания python 8 класс (задания по python для 8 класса)
Типичные ошибки:
- Забывают преобразовать строку в число - возникает ошибка TypeError при попытке деления.
- Используют range(1, n) вместо range(1, n+1) - тогда само число не выводится.
Как оптимизировать перебор, чтобы программа работала быстрее для больших чисел?
Достаточно проверять числа до квадратного корня из n. Если i - делитель, то парный делитель - n // i. Это сокращает количество итераций с n до √n.
import math
n = int(input("Введите число: "))
for i in range(1, int(math.isqrt(n)) + 1):
if n % i == 0:
print(i)
if i != n // i:
print(n // i)Проблемы:
- Делители выводятся не в порядке возрастания (сначала маленькие, потом большие). Для упорядоченного вывода нужно собрать их в список и отсортировать.
- Ошибка при использовании math.sqrt вместо math.isqrt - результат может быть неточным для больших чисел (потеря точности из-за float). math.isqrt гарантирует целое число.
Как записать решение в одну строку с помощью list comprehension?
Список делителей можно создать выражением [i for i in range(1, n+1) if n % i == 0]. Это компактно, но не оптимизировано.
n = int(input("Введите число: "))
divisors = [i for i in range(1, n+1) if n % i == 0]
print("Делители:", divisors)Для квадратичной оптимизации с tuple comprehension не получится, так как нужно добавлять оба делителя.
Как оформить поиск делителей в виде функции для многократного использования?
Функция принимает число и возвращает список делителей. Удобно для дальнейшего использования в других программах.
def get_divisors(n):
"""Возвращает список всех делителей числа n"""
divisors = []
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
divisors.append(i)
if i != n // i:
divisors.append(n // i)
return sorted(divisors)
n = int(input("Число: "))
print("Делители:", get_divisors(n))Распространённые ошибки:
- Не используют sorted() - результат будет неупорядоченным.
- Путают порядок добавления: сначала парный делитель, потом основной - теряется симметрия.
Как обработать ввод некорректных данных (не число, отрицательное число)?
Использовать конструкцию try-except для перехвата ValueError при преобразовании в int. Для отрицательных чисел задача не имеет смысла - можно потребовать повторный ввод.
while True:
try:
n = int(input("Введите положительное целое число: "))
if n > 0:
break
else:
print("Число должно быть положительным.")
except ValueError:
print("Ошибка: введите целое число.")
# Далее поиск делителейТипичная ошибка:
- Забывают про бесконечный цикл - если пользователь вводит неверные данные, программа не завершается. Это правильно, но нужно предусмотреть выход по пустому вводу или команде 'exit'.
Расширенные примеры по теме делителей числа
Пример 1: Нахождение суммы делителей
def sum_divisors(n):
total = 0
for i in range(1, int(n**0.5) + 1):
if n % i == 0:
total += i
if i != n // i:
total += n // i
return total
print(sum_divisors(12)) # 1+2+3+4+6+12 = 2828
Пример 2: Проверка, является ли число совершенным (сумма делителей равна числу)
def is_perfect(n):
if n <= 1:
return False
return sum_divisors(n) == n
for num in range(1, 10001):
if is_perfect(num):
print(num, end=' ')
# 6, 28, 496, 81286 28 496 8128
Пример 3: Вывод всех простых чисел до заданного предела с помощью решета Эратосфена
def sieve_of_eratosthenes(limit):
is_prime = [True] * (limit + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(limit**0.5) + 1):
if is_prime[i]:
for j in range(i*i, limit + 1, i):
is_prime[j] = False
return [num for num, prime in enumerate(is_prime) if prime]
print(sieve_of_eratosthenes(30))[2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
Пример 4: Подсчёт количества делителей с использованием разложения на простые множители
from collections import Counter
def prime_factors(n):
i = 2
factors = []
while i * i <= n:
while n % i == 0:
factors.append(i)
n //= i
i += 1
if n > 1:
factors.append(n)
return factors
def count_divisors(n):
factors = prime_factors(n)
counter = Counter(factors)
count = 1
for exp in counter.values():
count *= (exp + 1)
return count
print(count_divisors(144)) # 144 = 2^4 * 3^2 -> (4+1)*(2+1)=1515
Пример 5: Использование math.isqrt для точного квадратного корня (Python 3.8+)
import math
n = 1000000
sqrt_n = math.isqrt(n)
print(sqrt_n) # 1000
# Сравнение с math.sqrt: int(math.sqrt(n)) может дать 999 из-за округления1000
Пример 6: Генерация всех делителей с помощью рекурсии (экзотический способ)
def all_divisors_rec(n, i=1):
if i > n:
return []
if n % i == 0:
return [i] + all_divisors_rec(n, i+1)
else:
return all_divisors_rec(n, i+1)
print(all_divisors_rec(18)) # [1, 2, 3, 6, 9, 18][1, 2, 3, 6, 9, 18]
Пример 7: Поиск наибольшего общего делителя (НОД) через алгоритм Евклида - обратная задача
def gcd(a, b):
while b:
a, b = b, a % b
return a
print(gcd(48, 18)) # 66