Поиск делителей —Каталог задач по ЕГЭ - Информатика

Ошибка.
Попробуйте повторить позже

Задача 1#61487

Найдите все натуральные числа, принадлежащие отрезку [ $33$ $333$ $333$ ; $333$ $333$ $333$ ], у которых ровно $7$ различных четных делителей. В ответе укажите количество данных чисел.

Показать ответ и решение

Если число имеет разложение вида $a a 2a ⋅p11⋅p22⋅$ ... $⋅pann$ , то количество чётных делителей такого числа равно $a ⋅(a1 + 1)⋅(a2 + 1)⋅$ ... $⋅(an + 1)$ (выбрали степень двойки от $1$ до $a$ , степень каждого простого от $0$ до $ai$ ). По условию это равно $7$ — простое число, как произведение натуральных чисел его можно представить как $7$ или $1 ⋅7$ .

Случай $1$ : $a = 7$ , все $ai = 0 →$ число равно $27 = 128$ , не подходит.

Случай $2$ : $a = 1$ , какое-то $ai = 6$ , все остальные $ai = 0$ — приходим к разложению вида $2 ⋅p6$ .

На частном случае решение будет выглядеть так:

С помощью стандартной программы найдем подходящие нам числа до $100$ $000$ для того, чтобы рассмотреть их:

def dividers(n):
    k = 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if i % 2 == 0:
                k += 1
            if (n // i) % 2 == 0 and n // i != i:
                k += 1
    return k

for i in range(1, 100000):
    if dividers(i) == 7:
        print(i)

Подходящие нам числа в диапазоне до $100$ $000$ - это $128$ , $1458$ и $31250$ . Хочется разложить эти числа:

$128 = 27 = 2⋅26$

$1458 = 2 ⋅36$

$31250 = 2 ⋅56$

Заметим, что все числа раскладываются на $6 2⋅p$ , где $p$ - простое число.

Воспользуемся выведенной формулой для решения:

def prime(x):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

ans = 0
for i in range(int((33333333 // 2)**(1/6)), int((333333333 // 2)**(1/6)) + 1):
    if prime(i):
        if 33333333 <= 2*(i**6) <= 333333333:
            ans += 1
print(ans)

Ответ: 3

Ошибка.
Попробуйте повторить позже

Задача 2#61485

Найдите все натуральные числа, принадлежащие отрезку [11 111 111; 77 777 777], у которых ровно $5$ различных делителей. В ответе укажите количество данных чисел.

Показать ответ и решение

def prime(x):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

ans = 0
for i in range(int(11111111**0.25), int((77777777+1)**0.25)+1):
    if prime(i):
        ans += 1
print(ans)

Ответ: 8

Ошибка.
Попробуйте повторить позже

Задача 3#38815

Напишите программу, которая получает на вход число и возвращает количество его делителей. В ответе укажите количество делителей для числа $2004052336$ .

Показать ответ и решение

Решение 1

count = 0
x = int(input())
for i in range(1, int(x ** 0.5) + 1):
    if x % i == 0:
        count += 1
        if x // i != i:
            count += 1
print(count)

Решение 2

a = set()
x = int(input())
for i in range(1, int(x ** 0.5) + 1):
    if x % i == 0:
        a.add(i)
        a.add(x // i)
print(len(a))

Ответ: 60

Ошибка.
Попробуйте повторить позже

Задача 4#38813

Дано число $X = 1052336$ и массив с числами $a = [1,2,98,43,89,739]$ . Назовем «подходящими» элементы массива, которые являются делителями числа $X$ . Найдите сумму чисел, которые в паре с «подходящими» элементами массива дают произведение равное $X$ .

Показать ответ и решение


a = [1, 2, 98, 43, 89, 739]
x = 1052336
summa = 0
for i in a:
    if x % i == 0:
        summa += x // i
print(summa)

Ответ: 1591752

Ошибка.
Попробуйте повторить позже

Задача 5#38812

Для $X = 3052336$ найдите разность между количеством делителей числа $X$ , которые больше квадратного корня из $X$ и количеством делителей числа $X$ , которые меньше квадратного корня из $X$ . В ответе укажите искомую разность.

Показать ответ и решение

Обратим внимание, что если $d$ - делитель числа $X$ , то и $X ∕∕d$ - делитель числа $X$ . Очевидно, эти два числа находятся по разную сторону от $√-- X$ (иначе, предположим, что они оба меньше, тогда $X = d∗ X∕∕d < √x-∗√x-< X,$ чего явно не может быть, случай, когда оба больше - аналогичен). Таким образом, мы видим, что все делители разбиваются на пары, в которых один делитель меньше корня, а другой - больше. Отсюда понимаем, что делителей, меньших корня столько же, сколько и больших.

print(0)

А теперь представим, что мы не знаем математику, и попробуем решить это другим способом:

x = 3052336
sq = x ** 0.5
more = 0
less = 0
for i in range(1, x + 1):
    if x % i == 0:
        if i > sq:
            more += 1
        if i < sq:
            less += 1
print(more - less)

Ответ: 0

Ошибка.
Попробуйте повторить позже

Задача 6#38811

Утверждается, что количество делителей числа $X$ четно. Найдите количество пар делителей числа $X = 2052336$ , произведение которых равно исходному числу. При этом пары делителей выбираются следующим образом минимальный делитель * максимальный делитель, предминимальный делитель * предмаксимальный делитель и т.д. В ответе укажите два числа через пробел: сначала количество рассматриваемых пар, затем количеством пар, произведение которых равно исходному числу.

Показать ответ и решение

a = []
x = 2052336
for i in range(1, x + 1):
    if x % i == 0:
        a.append(i)
count = 0
n = len(a)
for i in range(n // 2):
    if a[i] * a[n - i - 1] == x:
        count += 1
print(n // 2, count)

Ответ: 60 60

Ошибка.
Попробуйте повторить позже

Задача 7#30249

Назовём числа $a$ и $b$ числами-близнецами, если $|a − b| = 2$ .

Найдите наименьшее натуральное число, имеющее ровно 512 делителей, простые делители которого образуют не менее трёх пар чисел-близнецов. В ответе укажите число, а также все его простые делители.

Показать ответ и решение

from itertools import combinations_with_replacement


def prime(x):
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            return False
    return True


def count_del(x):
    ans = []
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            ans += [i]
            ans += [x // i]
    return sorted(list(set(ans)))


def check(a):
    ans = 1
    for i in range(len(a)):
        ans *= a[i]
        if ans > 512:
            return False
    return ans == 512


dels = count_del(512)
primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29]
# Если скобок 9 штук и каждое альфа равно 1
minim = 2 ** 511
# Если скобок 9 штук и каждое альфа равно 1
t = 1
degrees = [2] * 9
for k in range(len(degrees)):
    t *= (primes[k] ** (degrees[k] - 1))
minim = min(minim, t)
# Все остальные случаи
                                                                                                     
                                                                                                     
for j in range(2, 9):
    for i in combinations_with_replacement(dels, j):
        if check(i):
            t = 1
            degrees = i[::-1]
            for k in range(len(degrees)):
                t = t * (primes[k] ** (degrees[k] - 1))
            minim = min(minim, t)
print(minim, *[i for i in count_del(minim) if prime(i)])

Ответ: 17297280 2 3 5 7 11 13

Ошибка.
Попробуйте повторить позже

Задача 8#30248

Найдите максимальное число на отрезке [1010101; 101010101], имеющее ровно 128 делителей, которое будет кратно 16. Выведите на экран в первой строке найденное число, а во второй все его нечетные делители в порядке возрастания.

Показать ответ и решение

def count_del(x):
    ans = [1, x]
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            ans += [i]
            if i != x // i:
                ans += [x//i]
        if len(ans) > 128:
            return ans
    return ans
for i in range(101010101, 1010101-1, -1):
    if len(count_del(i)) == 128 and i % 16 == 0:
        print(i, *sorted([i for i in count_del(i) if i % 2 != 0]))
        break

Ответ: 101008512 1 3 9 11 27 33 99 297 2657 7971 23913 29227 71739 87681 263043 789129

Ошибка.
Попробуйте повторить позже

Задача 9#30246

Найдите наибольшее натуральное число на отрезке $[10000;5000000]$ , которое имеет ровно $10$ делителей. В ответе укажите число.

Показать ответ и решение

def divs(n):
    count = 0
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            count += 1
            if i!=n//i:
                count += 1
    return count
for x in range(5000000, 10000 - 1, -1):
    if divs(x) == 10:
        print(x)
        break

Ответ: 4999563

Ошибка.
Попробуйте повторить позже

Задача 10#30245

Найдите наименьшее натуральное число, которое имеет ровно $20$ делителей. В ответе укажите число.

Показать ответ и решение

from itertools import combinations_with_replacement
def prime(x):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True
def count_del(x):
    ans = []
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            ans += [i]
            ans += [x//i]
    return sorted(list(set(ans)))
def check(a):
    ans = 1
    for i in range(len(a)):
        ans *= a[i]
        if ans > 20:
            return False
    return ans == 20
dels = count_del(20)
primes = [i for i in range(2, 100) if prime(i)]
#Если одна скобка
minim = 2**19
#Все остальные случаи
for j in range(2, 4):
    for i in combinations_with_replacement(dels, j):
        if check(i):
            t = 1
            degrees = i[::-1]
            for k in range(len(degrees)):
                t = t * (primes[k] ** (degrees[k]-1))
            minim = min(minim, t)
print(minim)

Ответ: 240

Ошибка.
Попробуйте повторить позже

Задача 11#30244

Найдите все натуральные числа, принадлежащие отрезку [ $33$ $333$ $333$ ; $99$ $999$ $999$ ], у которых ровно $7$ различных четных делителей. В ответе укажите количество данных чисел.

Показать ответ и решение

Если число имеет разложение вида $a a 2a ⋅p11⋅p22⋅$ ... $⋅pann$ , то количество чётных делителей такого числа равно $a ⋅(a1 + 1)⋅(a2 + 1)⋅$ ... $⋅(an + 1)$ (выбрали степень двойки от $1$ до $a$ , степень каждого простого от $0$ до $ai$ ). По условию это равно $7$ — простое число, как произведение натуральных чисел его можно представить как $7$ или $1 ⋅7$ .

Случай $1$ : $a = 7$ , все $ai = 0 →$ число равно $27 = 128$ , не подходит.

Случай $2$ : $a = 1$ , какое-то $ai = 6$ , все остальные $ai = 0$ — приходим к разложению вида $2 ⋅p6$ .

На частном случае решение будет выглядеть так:

С помощью стандартной программы найдем подходящие нам числа до $100$ $000$ для того, чтобы рассмотреть их:

def dividers(n):
    k = 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if i % 2 == 0:
                k += 1
            if (n // i) % 2 == 0 and n // i != i:
                k += 1
    return k

for i in range(1, 100000):
    if dividers(i) == 7:
        print(i)

Подходящие нам числа в диапазоне до $100$ $000$ - это $128$ , $1458$ и $31250$ . Хочется разложить эти числа:

$128 = 27 = 2⋅26$

$1458 = 2 ⋅36$

$31250 = 2 ⋅56$

Заметим, что все числа раскладываются на $6 2⋅p$ , где $p$ - простое число.

Воспользуемся выведенной формулой для решения:

def prime(x):
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            return False
    return True

ans = 0
for i in range(int((33333333 // 2)**(1/6)), int((99999999 // 2)**(1/6)) + 1):
    if prime(i):
        if 33333333 <= 2*(i**6) <= 99999999:
            ans += 1
print(ans)

Ответ: 2

Ошибка.
Попробуйте повторить позже

Задача 12#30243

Найдите все натуральные числа, принадлежащие отрезку [ $33$ $222$ $555$ ; $99$ $888$ $999$ ], у которых ровно $3$ различных нечётных делителя (количество чётных делителей может быть любым). В ответе укажите количество данных чисел.

Показать ответ и решение

def is_prime(n):
    if n <= 1:
        return False
    for j in range(2, int(n ** 0.5) + 1):
        if n % j == 0:
            return False
    return True

ans = 0
for j in range(3, 10000):
    if is_prime(j):
        for i in range(26):
            if 33222555 <= 2**i*j**2 <= 99888999:
                ans += 1
print(ans)

Ответ: 1793

Ошибка.
Попробуйте повторить позже

Задача 13#30215

Среди целых чисел, принадлежащих числовому отрезку $[333555;777999]$ , найдите числа, среди нетривиальных делителей которых есть ровно $38$ двузначных чисел. Для каждого найденного числа запишите в ответе само число, наименьший и наибольший из его двузначных делителей через пробел. Так, например, для числа $36$ учитываются только делители $12$ и $18$ .

Показать ответ и решение

def count_del(x):
    ans = []
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            if len(str(i)) == 2:
                ans += [i]
            if i != x // i:
                if len(str(x // i)) == 2:
                    ans += [x // i]
    return sorted(ans)


ans = 0
for i in range(333555, 777999 + 1):
    if len(count_del(i)) == 38:
        print(i, count_del(i)[0], count_del(i)[-1])

Ответ: 360360 10 99 776160 10 99

Ошибка.
Попробуйте повторить позже

Задача 14#30212

Число называется избыточным, если оно строго меньше суммы своих собственных делителей (то есть всех положительных делителей, отличных от самого числа). Определите количество избыточных чисел из диапазона [5; 50000].

Показать ответ и решение

def count_del(x):
    ans = [1]
    for i in range(2, int(x**0.5)+1):
        if x % i == 0:
            ans += [i]
            if i != x//i:
                ans += [x//i]
    return sum(ans) > x

ans = 0
for i in range(5, 50000+1):
    if count_del(i):
        ans += 1
print(ans)

Ответ: 12394

Ошибка.
Попробуйте повторить позже

Задача 15#30211

Определите количество составных натуральных чисел из диапазона $[3;30000]$ , у которых количество нетривиальных делителей не менее трех.

Примечание. Нетривиальный делитель — делитель, не равный единице и самому числу.

Показать ответ и решение

def count_del(x):
    ans = 0
    for i in range(2, int(x ** 0.5) + 1):
        if x % i == 0:
            ans += 1
            if i != x // i:
                ans += 1
        if ans >= 3:
            return True
    return False


ans = 0
for i in range(3, 30000 + 1):
    if count_del(i):
        ans += 1
print(ans)

Ответ: 19282

Ошибка.
Попробуйте повторить позже

Задача 16#30209

Найти минимальное число, большее $156239$ , которое имеет ровно $60$ делителей, из которых ровно $4$ – простые. В ответе запишите все простые делители найденного числа в порядке возрастания.

Показать ответ и решение

def prime(n):
    if n == 1: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def okay(n):
    k, k_pr = 0, 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            k += 1
            if prime(i):
                k_pr += 1
            if n // i != i:
                k += 1
                if prime(n // i):
                    k_pr += 1
    if k == 60 and k_pr == 4:
        return True
    return False

def prime_divs(n):
    a = []
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            if prime(i):
                a.append(i)
            if n // i != i and prime(n // i):
                a.append(n // i)
    a.sort()
    return a

ans = 0
for i in range(156239, 10000000):
    if okay(i):
        ans = i
        break
print(*prime_divs(ans))

Ответ: 2 5 17 23

Ошибка.
Попробуйте повторить позже

Задача 17#30208

Назовем число добрым, если среди его делителей есть хотя бы три квадрата простых чисел. Найти 5 минимальных добрых чисел, больших $21317$ . В ответе запишите найденные числа через пробел в порядке возрастания.

Показать ответ и решение

def prime(n):
    if n == 1: return False
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            return False
    return True

def okay(n):
    k = 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            if int(i ** 0.5) == i ** 0.5 and prime(i ** 0.5):
                k += 1
            if n // i != i:
                x = n // i
                if int(x ** 0.5) == x ** 0.5 and prime(x ** 0.5):
                    k += 1
        if k >= 3:
            return True
    return False

counter = 0
for i in range(21317, 100000000):
    if okay(i):
        print(i, end=’ ’)
        counter += 1
    if counter == 5:
        break

Ответ: 21600 21780 22050 22500 22932

Ошибка.
Попробуйте повторить позже

Задача 18#30207

Найти на промежутке $[123123,321321]$ числа, которые нацело делится на целую часть среднего арифметического своих делителей. В ответе запишите количество таких чисел и их произведение.

Показать ответ и решение

def average(n):  # делится ли на целую часть ср .ариф. делителей
    k, s = 0, 0
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            k += 1
            s += i
            if n // i != i:
                k += 1
                s += n // i
    if n % int(s / k) == 0:
        return True
    return False

counter, p = 0, 1
for i in range(123123, 321322):
    if average(i):
        counter += 1
        p *= i
print(counter, p)

Ответ: 5 352861289574854860800000000

Ошибка.
Попробуйте повторить позже

Задача 19#30204

Назовем число красивым, если оно делится на сумму своих цифр и имеет ровно 6 нетривиальных делителей. Найти на промежутке $[51242,421421]$ количество красивых чисел и их среднее арифметическое. В ответе запишите два числа через пробел: сначала количество чисел, потом целую часть их среднего арифметического.

Показать ответ и решение

def sum_digits(n):  # сумма цифр
    s = 0
    while n > 0:
        s += n % 10
        n //= 10
    return s

def count_div(n):
    k = 0
    for i in range(2, int(n ** 0.5) + 1):
        if n % i == 0:
            k += 1
            if n // i != i:
                k += 1
    return k

counter, summ = 0, 0
for i in range(51242, 421422):
    if i % sum_digits(i) == 0 and count_div(i) == 6:
        counter += 1
        summ += i
print(counter, int(summ / counter))

Ответ: 3519 228061

Ошибка.
Попробуйте повторить позже

Задача 20#30202

Найти числа из промежутка $[750000,930000]$ , у которых есть ровно 3 натуральных делителя, которые делятся на 17. В ответе запишите эти числа и три минимальных делителя каждого числа (делители должны идти по возрастанию). Ответ запишите в формате:

Число1, Дел1, Дел2, Дел3; Число2, Дел1, Дел2, Дел3; и т.д. (После каждой запятой или точки с запятой ставится пробел, каждая группа (число и его три минимальных делителя) отделяется от следующей группы точкой с запятой, после последней группы никакой знак не ставится).

Показать ответ и решение

def only_3_div_kr_17(n):
    a = []  # массив делителей
    k17 = 0  # счетчик делителей, кратных 17
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            a.append(i)
            if i % 17 == 0:
                k17 += 1
            if n // i != i:
                a.append(n// i)
                if (n // i) % 17 == 0:
                    k17 += 1
        if k17 > 3:  # уже нашли больше 3 делителей, кратных 17
            return False, []  # Число не подходит, вернем пустой массив
    if k17 < 3:  # не нашли 3 делителя, кратных 17
         return False, []
    if k17 == 3:
        a.sort()
        return True, a[:3]  # a[:3] - срез массива, 3 минимальных делителя
    # Функция возвращает кортеж, где нулевой элемент - True/False,
    # первый элемент - три минимальных делителя

for i in range(750000, 930000):
    h = only_3_div_kr_17(i)
    if h[0] == True:  # если число подходит
        divs = h[1]  # три минимальных делителя
        print(i, *divs, sep=’, ’, end=’; ’)
        # при копировании ответа не копируем последнюю ;

Ответ: 756857, 1, 17, 211; 845393, 1, 17, 223; 875993, 1, 17, 227; 891497, 1, 17, 229; 922913, 1, 17, 233