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

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

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

Например, маске 123*4?5 соответствуют числа 123405 и 12300425.

Среди натуральных чисел, не превышающих 10⁷, найдите все числа, соответствующие маске 12*4*8?, которые представляют собой произведение двух различных простых делителей, причём сумма этих делителей – простое число. В ответе запишите все найденные числа в порядке возрастания, справа от каждого числа – сумму его простых делителей.

Решение

Анализ соответствия числа маске выполняется быстрее, чем перебор делителей с дополнительным анализом на простоту. Поэтому, перебирая числа от минимального значения, соответствующего маске, 12480 до максимального 1299489 (любое большее число маске соответствовать не будет, а таких чисел 87%), сначала будем проверять число на соответствие маске, а потом, на условие с простыми делителями. Обратный порядок анализа на Python будет работать в десятки раз медленнее. Анализировать соответствие числа маске можно через целочисленные операции или через анализ строки. На Python в анализе через строки возможно использование библиотеки fnmatch, но для данной маски числа программа будет работать в несколько раз медленнее.

Python анализ целочисленными операциями

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


for n in range(12480, 1299490):
    if n // 10 % 10 == 8:
        flag4 = False
        z = n // 100
        while z > 99:
            if z % 10 == 4:
                flag4 = True;
            z //= 10
        if z == 12 and flag4:
            for i in range(2, int(n ** 0.5) + 1):
                if n % i == 0:
                    if simple(i) and simple (n // i) and simple(i + n // i):
                        print(n, i + n // i)
                    else:
                        break;

Python анализ через строки

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


for n in range(12480, 1299490):
    s = str(n)
    if s[:2] == '12' and s[-2] == '8' and '4' in s[2: -2]:
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                if simple(i) and simple (n // i) and simple(i + n // i):
                    print(n, i + n // i)
                else:
                    break;

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 n in range(12480, 1299490):
    if fnmatch(str(n), '12*4*8?'):
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                if simple(i) and simple (n // i) and simple(i + n // i):
                    print(n, i + n // i)
                else:
                    break;

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: Integer;
    flag4: Boolean;
begin
    for n := 12480 to 1299489 do
    begin
        if n div 10 mod 10 = 8  then
        begin
            flag4 := False;
            z := n div 100;
            while z > 99 do
            begin
                if z mod 10 = 4 then
                    flag4 := True;
                z := z div 10;
            end;
            if (z = 12) and flag4 then
                for i := 2 to round(sqrt(n)) do
                    if n mod i = 0 then
                        if simple(i) and simple(n div i) and simple(i + n div i) then
                            Writeln(n, ' ', i + n div i)
                        else
                            break;
        end;
    end;
end.

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, i: Integer;
    s: String;
begin
    for n := 12480 to 1299489 do
    begin
        s := IntToStr(n);
        if (s[:3] = '12') and (s[s.Length - 1] = '8') and s[3:s.Length - 1].Contains('4')  then
            for i := 2 to round(sqrt(n)) do
                if n mod i = 0 then
                    if simple(i) and simple(n div i) and simple(i + n div i) then
                        Writeln(n, ' ', i + n div i)
                    else
                        break;
    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 n = 12480; n < 1299490; n++)
    {
        if (n / 10 % 10 == 8)
        {
            bool flag4 = false;
            int z = n / 100;
            while (z > 99)
            {
                if (z % 10 == 4)
                    flag4 = true;
                z /= 10;
            }
            if (z == 12 && flag4)
            {
                for (int i = 2; i <= sqrt(n); i++)
                    if (n % i == 0)
                        if (simple(i) && simple(n / i) && simple(i + n / i))
                            cout << n << " " << i + n / i << endl;
                        else
                            break;
            }
        }
    }
}

C++ анализ через строки

#include <iostream>
#include <string>
#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 n = 12480; n < 1299490; n++)
    {
        string s = to_string(n);
        if (s.substr(0, 2) == "12" && s[s.length() - 2] == '8' && s.substr(2, s.length() - 4).find("4") != -1)
        {
            for (int i = 2; i <= sqrt(n); i++)
                if (n % i == 0)
                    if (simple(i) && simple(n / i) && simple(i + n / i))
                        cout << n << " " << i + n / i << endl;
                    else
                        break;
        }
    }
}

Ответ

124282 62143
1204282 602143
1214182 607093
1224082 612043
1229482 614743
1244482 622243
1295482 647743