Задача 6226. Источник: Поляков. Задание КИМ 25

Страница задачи 6226

(А. Богданов) Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.

Найдите все натуральные числа, не превышающие 10¹⁰, которые соответствуют маске 1?2*0*2?1 и при этом содержат ровно три делителя. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа запишите его второй по величине делитель.

Решение

Ровно три делителя имеют числа, являющиеся квадратом простого числа. Будем перебирать диапазон от 1011 (первый целочисленный квадратный корень после минимального числа, соответствующего шаблону) до 100000 и для простых чисел из этого диапазона проверять, соответствует ли квадрат числа шаблону. Для дополнительного ускорения программы можно перебирать только нечетные числа, т.к. четные простыми являться не будут. Соответствие шаблону удобнее проверять через целочисленные операции и флаговые переменные. На Python проверку на соответствие шаблону можно осуществлять с использование библиотеки fnmatch. Вторым делителем будет являться само простое число.

Python с использованием библиотеки fnmatch

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


from fnmatch import fnmatch
for i in range(1011, 100001, 2):
    if simple(i):
        n=i**2
        if fnmatch(str(n),'1?2*0*2?1'):
            print(n, i)

Python

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


for i in range(1011, 100001, 2):
    if simple(i):
        n = i ** 2
        if n % 10 == 1:
            flag0 = False
            flag2 = False
            z = n // 100
            while z >= 10000:
                if z % 10 == 2:
                    flag2 = True
                    z //= 10
                    break
                z //= 10
            while z >= 1000:
                if z % 10 == 0:
                    flag0 = True
                z //= 10
            if flag2 and flag0 and z % 10 == 2 and z // 100 == 1:
                print(n, i)

PascalABC

function simple(n: Integer): Boolean;
var
    i: Integer;
begin
    Result := True;
    for i := 2 to round(sqrt(n)) do
        if n mod i = 0 then
        begin
            Result := False;
            break;
        end;
end;

var
    n, z, i: Int64;
    flag0, flag2: Boolean;
begin
    for i := 1011 to 100000 do
        if simple(i) then
        begin
            n := i * i;
            if n mod 10 = 1 then
            begin
                flag0 := False;
                flag2 := False;
                z := n div 100;
                while z >= 10000 do
                begin
                    if z mod 10 = 2 then
                    begin
                        flag2 := True;
                        z := z div 10;
                        break;
                    end;
                    z := z div 10;
                end;
                while z >= 1000 do
                begin
                    if z mod 10 = 0 then
                        flag0 := True;
                    z := z div 10;
                end;
                if flag0 and flag2 and (z mod 10 = 2) and (z div 100 = 1) then
                    Writeln(n, ' ', i);
            end;
        end;
end.

C++

#include <iostream>
#include <cmath>
using namespace std;
bool simple(int n)
{
    for (int i = 2; i <= sqrt(n); i++)
        if (n % i == 0)
            return false;
    return true;
}
int main()
{
	for (int i = 1011; i <= 100000; i += 2)
        if (simple(i))
        {
            long long n = (long long)i * i;
            if (n % 10 == 1)
            {
                bool flag0 = false, flag2 = false;
                long long z = n / 100;
                while (z >= 10000)
                {
                    if (z % 10 == 2)
                    {
                        flag2 = true;
                        z /= 10;
                        break;
                    }
                    z /= 10;
                }
                while (z >= 1000)
                {
                    if (z % 10 == 0)
                        flag0 = true;
                    z /= 10;
                }
                if (flag0 && flag2 && z % 10 == 2 && z / 100 == 1)
                    cout << n << " " << i << endl;
            }
        }
}

Ответ

152004241 12329
1129027201 33601
1320668281 36341
1628203201 40351