Задание 25

Обработка целых чисел

Типов: 10

Как распознать

M равна сумме минимального и максимального делителей без 1 и числа.

Условие

Найти первые пять чисел больше 800000, у которых M оканчивается на 4.

Разбор

Собери делители попарно до квадратного корня.

Шаблон

def find_M(x):
    deliteli = set()
    for d in range(2,int(x**0.5)+1):
        if x%d==0:
            deliteli.add(d)
            deliteli.add(x//d)
    if len(deliteli)==0:
        return 0
    return min(deliteli)+max(deliteli)
cnt = 0
for x in range(800001,801000):
    M = find_M(x)
    if cnt == 5:
        break
    else:
        if M%10 == 4:
            print(x,M)
            cnt+=1

Как распознать

Число является произведением двух простых множителей, каждый содержит одну 5.

Условие

Найти первые пять чисел больше 1324727 и вывести больший множитель.

Разбор

Проверь простоту обеих частей каждой пары делителей.

Шаблон

def is_prime(x):
    return x>1 and all(x%d!=0 for d in range(2,int(x**0.5)+1))
def f(x):
    D = []
    for i in range(1,int(x**0.5)+1):
        if x%i==0:
            if is_prime(i) and is_prime(x//i):
                if str(i).count("5")==1 and str(x//i).count("5")==1:
                    D.append(i)
                    D.append(x//i)
    return D
cnt = 0
for x in range(1324728,1325728):
    if cnt==5:
        break
    else:
        Dx = f(x)
        if len(Dx)==2:
            print(x,max(Dx))
            cnt+=1

Как распознать

Маска содержит ? и *.

Условие

Найти числа до 10^10 по маске 3?12?14*5, кратные 1917.

Разбор

Перебирай только кратные и проверяй fnmatch.

Шаблон

from fnmatch import fnmatch
for x in range(1917,10**10+1,1917):
    if fnmatch(str(x),"3?12?14*5"):
        print(x,x//1917)

Как распознать

Маска содержит ? и *.

Условие

Найти числа до 10^8 по маске 3?21*57, кратные 2023.

Разбор

Шаг цикла сразу обеспечивает делимость.

Шаблон

from fnmatch import *
for x in range(2023,10**8+1,2023):
    if fnmatch(str(x),"3?21*57"):
        print(x,x//2023)

Как распознать

Нужен отсортированный список делителей.

Условие

Универсальная вспомогательная функция.

Разбор

Добавляй найденный делитель вместе с парным.

Шаблон

def get_divisors(n):
    divisors = set()
    for i in range(1, int(n**0.5) + 1):
        if n % i == 0:
            divisors.add(i)
            divisors.add(n // i)
    return sorted(list(divisors))

Как распознать

Нужно проверить числа или делители на простоту.

Условие

Универсальная функция проверки простоты.

Разбор

Проверяй делители до квадратного корня.

Шаблон

def is_prime(x):
    return x>1 and all(x%d!=0 for d in range(2,int(x**0.5)+1))

Как распознать

Число соответствует маске 3*52? и имеет нечётное число делителей.

Условие

Найти подходящие числа до 10^7 и вывести максимальный собственный делитель.

Разбор

Построй список делителей; предпоследний элемент является максимальным собственным.

Шаблон

from fnmatch import *
def d(x):
    deliteli = set()
    for i in range(1,int(x**0.5)+1):
        if x%i==0:
            deliteli.add(i)
            deliteli.add(x//i)
    return sorted(list(deliteli))
for x in range(1,10**7):
    if fnmatch(str(x),"3*52?"):
        num = d(x)
        if len(num)%2!=0:
            print(x,num[-2])

Как распознать

Нужно найти числа по маске 1*2*7*04 с 45 делителями.

Условие

Вывести пять наименьших чисел больше 10^9 и их максимальные собственные делители.

Разбор

Нечётное число делителей бывает у квадратов, поэтому перебирай квадраты.

Шаблон

from fnmatch import *
def d(x):
    deliteli = set()
    for i in range(1,int(x**0.5)+1):
        if x%i==0:
            deliteli.add(i)
            deliteli.add(x//i)
    return sorted(list(deliteli))
cnt = 0
sqrt_x = int((10**9+1)**0.5)
while cnt <5:
    x = sqrt_x**2
    if fnmatch(str(x),"1*2*7*04"):
        D = d(x)
        if len(D)==45:
            cnt+=1
            print(x,D[-2])
    sqrt_x+=1

Как распознать

M равна сумме минимального и максимального простых делителей.

Условие

Найти первые пять чисел больше 5400000, где M > 60000 и M является палиндромом.

Разбор

Собери только простые делители и проверь строку M.

Шаблон

def is_prime(x):
    return x > 1 and all(x%d!=0 for d in range(2,int(x**0.5)+1))
def find_m(x):
    deliteli = set()
    for n in range(2,int(x**0.5)+1):
        if x%n==0:
            if is_prime(n):
                deliteli.add(n)
            if is_prime(x//n):
                deliteli.add(x//n)
    if len(deliteli)==0:return 0
    return min(deliteli)+max(deliteli)
cnt = 0
for x in range(5400001,5410000):
    if cnt == 5:
        break
    else:
        M = find_m(x)
        if M>60000 and str(M) == str(M)[::-1]:
            print(x,M)
            cnt+=1

Как распознать

Нужно вывести 1-е, 61-е, 121-е совпадение и далее.

Условие

Числа до 10^10 по маске 8*80*06, кратные 4546.

Разбор

Увеличивай счётчик только при совпадении с маской.

Шаблон

from fnmatch import *
num = 0
for x in range(4546,10**10,4546):
    if fnmatch(str(x),"8*80*06"):
        num+=1
        if (num-1)%60==0:
            print(x,x//4546)