ЕГЭ. Информатика. Задача 25

Автор: | 06.02.2024

Немного о делителях числа

1.Число делителей чисел равных квадрату некоторого числа.

Возьмем для примера числа 4^2=16; 17^2=289; 22^2=484

Для 16 делители будут 1, 2, 4, 8, 16. Число делителей= 5, а Сумма всех делителей = 31

Для числа 289 – делители 1, 17, 289 и число делителей= 3, а Сумма всех делителей = 307

Для числа 484 делители 1, 2, 4, 11, 22, 44, 121, 242, 484. Число делителей= 9, а Сумма всех делителей – 931

Обратите внимание, что квадрат некоторого числа всегда имеет нечетное число делителей, а произведение равноотстоящих Делителей от центра равно самому числу. Для квадратов чисел центральный элемент умножается сам на себя.

Поэтому, делители, отстоящие от центра вправо всегда можно найти, разделив число на найденный делитель числа слева от центра. информатика

Если Х искомое число, а найденный делитель равен Y , то симметричный найденному делитель справа = X/Y.

Из этого следует простое правило.  Не надо перебирать весь диапазон чисел заданного отрезка от 1 до этого числа, а достаточно искать делители в диапазоне от 1 до корня квадратного из числа Х.

Получается, что у каждого делителя есть своя пара. У единицы – это само число. Причём, один делитель из пары находится до корня, другой после корня. Исключением будет тот случай, когда из числа А извлекается целый корень. Тогда для этого корня не будет пары (парой и будет само это число √A * √A = A).

Проверим симметричность для чисел, не являющихся квадратом некоторого.

a) Для числа 24 имеем1, 2, 3, 4, 6, 8, 12, 24. Число делителей = 8, а Сумма всех делителей – 60

b) Для числа 172 имеем – 1, 2, 4, 43, 86, 172. Число делителей = 6, а Сумма всех делителей – 308

c) Для числа 567 имеем1, 3, 7, 9, 21, 27, 63, 81, 189, 567. Число делителей= 10, а Сумма всех делителей – 968

Видим, что в этом случае число всех делителей равно четному числу. При переборке чисел в цикле поэтому можно брать не весь заданный отрезок чисел, а от 1 до целой части из корня квадратного максимального числа +1

2.Определение числа делителей числа по его разложению на множители. Примеры.

N=720 и 720=24*32*51

Общее число делителей равно d(720)= (4+1)*2+1)*(1+1)=5*3*2=30

1 2 3 4 5 6 8 9 10 12 15 16 18 20 24 30 36 40 45 48 60 72 80 90 120 144 180 240 360 720

Сумма всех делителей будет равна (1+2+4+8+16)*(1+3+9)*(1+5)=31*13*6=

===========

N=567 и 567==34*71, тогда Общее число делителей d(567)=(4+1)*(1+1)=5*2=10

137921276381189 и 567 – все натуральные делители числа 567.

===========

N=3900

3900=22*31*52*131 и Общее число делителей равно d(3900)=2+1)*(1+1)*(2+1)*(1+1)=3*2*3*2=36

1234561012131520252630395052606575781001301501561952603003253906507809751 3001 9503 900

===========

3.Определение суммы всех делителей числа. Примеры.

N=120 и 120=23*31*51

S(120)=(1+2+4+8)(1+3)(1+5)=15*4*6=360

Где 2,4,8 степени числа 2 до максимальной, а 3 и 5 у нас в 1-ой степени

N=720 и 720=24*32*51

S(720)=(1+2+4+8+16)*(1+3+9)(1+5)=31*13*6=2418

Где 2,4,8,16 степени 2, а 3 и 9 степени 3

N=567 и 567=34*71, тогда S(567)=(1+3+9+27+81)(1+7)=121*8=968

Где 3,9,27,81 – степени 3 соответственно

Пример нахождения всех делителей числа, включая 1 и само число

#Нахождение делителей числа в цикле while
#Пример из egoroff-channel
n=int(input("Введите число - "))
i=1
a=[]
while i*i<=n: #Это равносильно i<=n**0.5
    if n%i==0:
        a.append(i)
        if i!=n//i:
            a.append(n//i)# Добавление симметричного делителя
    i+=1
a=sorted(a)
print(a)
print(*a)   #Вывод без скобок

Код программы с применение функции

#Нахождение делителей числа через функцию

#Пример из egoroff-channel
def f(n):
    lst=[]
    for i in range(1,int(n**0.5)+1):
        if n%i==0:
            lst.append(i)
            lst.append(n//i)
#Пример из egoroff-channel
    return sorted(set(lst)) #сортировка и выбор уникальных элементов
    
n=int(input("Введите число - "))
print(f(n))            

Код программы на питоне для подсчета количества делителей и их суммы

#Материал на основе стрима 16 Задача 25
#Общая задача-нахождение всех делителей чисел в диапазоне [126849;126871]
#Найдем пока все делители некоторого числа Х
x=567
c=0
s=0#Подсчет суммы всех делителей
for i in range(1,x+1):
    if x%i==0:
        c+=1
        s=s+i
        print(i,end=', ')
    
print("\nЧисло делителей=",c)
print("Сумма всех делителей -",s)

Код программы на питоне для подсчета количества делителей для небольшого диапазона чисел

#Общая задача-нахождение всех делителей чисел в диапазоне [126849;126871]
#Для нахождения чисел числа делителей из заданного диапазона вводим
#ещё один цикл по Х
#Программа выведем для каждого числа из диапазона число делителей
for x in range(126849,126871+1):
    c=0
    for i in range(1,x+1):
        if x%i==0:
            c+=1#Увеличиваем число найденных делителей на 1
    if c==4:        
        print(x," Число делителей = ",c)        
print("Но ведь нам нужно не только найти числа с 4-мя делителями, но и сами делители")
print("Проще выписать эти числа и для каждого из них найти делители вместо нашего примера Х=24")

Код программы на питоне для подсчета количества делителей и их вывод через строковую переменную

#Общая задача-нахождение всех делителей чисел в диапазоне [126849;126871]
#Для нахождения чисел числа делителей из заданного диапазона вводим
#ещё один цикл по Х
#Программа выведем для каждого числа из диапазона число делителей
for x in range(126849,126871+1):
    c=0
    #Добавляем строковую переменную для запоминания делителей
    s=''
    for i in range(1,x+1):
        if x%i==0:
            c+=1#Увеличиваем число найденных делителей на 1
            s=s+str(i)+" "
    if c==4:        
        print(x," Число делителей = ",c," Делители; ",s)    

Код программы на питоне для подсчета количества делителей и их вывод через создание списка

#Общая задача-нахождение всех делителей чисел в диапазоне [126849;126871]
for x in range(126849,126872):
    a=[]#Создаём пустой список
   
    for i in range(1,x+1):
        if x%i==0:
           a.append(i)
    len1=len(a)
    if len1==4:        
        print(x," Число делителей = ",len1," Делители; ",a)  

Проблема нахождения тривиальных и нетривиальных делителей, минимального их них или максимального, отсортированного по возрастанию или убыванию резко усложняется, если рассматриваемый диапазон чисел для нахождения делителей очень большой.

Задача 128. Назовем нетривиальными делители натурального числа его делитель не равный 1 и самому числу.

Найдите все натуральные числа, принадлежащие отрезку [4234678;10157812] и имеющих ровно 3 нетривиальных делителя.

#Задача 128
#Найдите все натуральные числа в диапазоне [4234679;10157812]
#и имеющие ровно 3 нетривиальных делителя
for x in range(4234679,10157813):
    a=[]#Создаём пустой список
    if x**0.5==int(x**0.5):#Число является полным квадратом   
        for i in range(1,int(x**0.5)+1):#Ищем от 1 
            if x%i==0:
               a.append(i)
            if len(a)>3:#
               break #Прерываем
    
    if len(a)==3:        
        print(x)
   

Программа должна вывести 2 числа: 4879681 и 7898481

Программа ниже добавляет и делитель за центром, но он повторится. т.к. это корень некоторого найденного числа х диапазона чисел.

Команда print(a) выведем и скобки списка делителей

#Найдите все натуральные числа, принадлежащие отрезку
#[4234678;10157812] и имеющих ровно 3 нетривиальных делителя.

for x in range(4234679,10157813):
    a=[]#Определяем пустой список
    if x**0.5==int(x**0.5):# Условие квадрата числа
        for i in range(2,int(x**0.5)+1): 
            if x%i==0: #делитель найден
                a.append(i) #Добавляем  делитель
                a.append(x//i)#Добавление симметричного делителя за центром
            if len(a)>4:
                break
    if len(a)==4:
        print(x,*a)

Программа выведет

4879681 47 103823 2209 2209 Максимальный делитель= 103823
7890481 53 148877 2809 2809 Максимальный делитель= 148877

#Найдите все натуральные числа, принадлежащие отрезку
#[4234678;10157812] и имеющих ровно 3 нетривиальных делителя.
#Решение через использование множества
for x in range(4234679,10157813):
    a=set()#Определяем пустое множество
    if x**0.5==int(x**0.5):# Условие квадрата числа
        for i in range(2,int(x**0.5)+1):#Т.к. ищем нечетное число делителей
            if x%i==0: #делитель найден
                a.add(i) #Добавляем  делитель
                a.add(x//i)#Добавление симметрично делителя
            if len(a)>3:
                break
    if len(a)==3:
        print(x,"Делители-",*a,"Максимальный делитель",max(a))

Программа выведет

4879681 Делители- 103823 2209 47 Максимальный делитель 103823
7890481 Делители- 2809 53 148877 Максимальный делитель 148877

Обратите внимание, что при добавлении во множество остаются лишь уникальные элементы