Для решения задачи необходимо определить, сколько чисел на интервале [a, b] имеют ровно 8 различных делителей. Число имеет 8 различных делителей, если оно может быть выражено в одной из следующих форм:
- ( n = p^7 ) (где ( p ) — простое число)
- ( n = p^3 \cdot q ) (где ( p ) и ( q ) — различные простые числа)
- ( n = p^1 \cdot q^1 \cdot r^1 ) (где ( p, q, r ) — три различных простых числа)
Теперь, давайте перепишем программу на языке Python, которая будет подготавливать данные для заданного интервала и считать количество таких чисел.
def prime_sieve(limit):
is_prime = [True] * (limit + 1)
p = 2
while (p * p <= limit):
if (is_prime[p]):
for i in range(p * p, limit + 1, p):
is_prime[i] = False
p += 1
return [p for p in range(2, limit + 1) if is_prime[p]]
def count_divisors(n, primes):
count = 1
for p in primes:
if p * p > n:
break
exp = 0
while n % p == 0:
n //= p
exp += 1
count *= (exp + 1)
if n > 1: # n is prime
count *= 2
return count
def count_numbers_with_8_divisors(a, b):
primes = prime_sieve(b)
count = 0
for n in range(a, b + 1):
if count_divisors(n, primes) == 8:
count += 1
return count if count > 0 else -1
# Входные данные
a = 10
b = 14953
# Вычисление количества чисел с 8 делителями
result = count_numbers_with_8_divisors(a, b)
print(result)
Эта программа делает следующее:
- Генерирует список простых чисел до ( b ) с помощью решета Эратосфена.
- Определяет количество делителей каждого числа в заданном интервале.
- Подсчитывает количество чисел, имеющих ровно 8 делителей и выводит результат.
Запустив эту программу, вы получите количество чисел на интервале от 10 до 14953, у которых есть ровно 8 различных делителей.
