Программное решение задач ЕГЭ по информатике

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

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

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

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

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

Решение

Начиная с минимального числа соответствующего маске 1205500, найдем минимальное число, кратное 311 и далее будем перебирать числа с данным шагом до максимального числа удовлетворяющего маске 12959599. Каждое число будем сначала анализировать на соответствие маске, а потом на делители, т.к. проверка соответствия маске будет выполняться быстрее. Проверку соответствия числа маске можно осуществлять через целочисленные операции или через анализ строки. При анализе через строки на Python возможно использование библиотеки fnmatch.

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

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


z = 1205500
while z % 311 != 0:
    z += 1
for n in range(z, 12959600, 311):
    if n // 100 % 10 == 5:
        z = n // 1000
        while z > 9999:
            z //= 10
        if z // 100 == 12 and z % 10 == 5:
            for i in range(2, int(n ** 0.5) + 1):
                if n % i == 0:
                    if simple(i) and simple (n // i):
                        print(n, n // 311)
                    else:
                        break;

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

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


z = 1205500
while z % 311 != 0:
    z += 1
for n in range(z, 12959600, 311):
    s = str(n)
    if s[:2] == '12' and s[3] == '5' and s[-3] == '5':
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                if simple(i) and simple (n // i):
                    print(n, n // 311)
                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
z = 1205500
while z % 311 != 0:
    z += 1
for n in range(z, 12959600, 311):
    if fnmatch(str(n), '12?5*5??'):
        for i in range(2, int(n ** 0.5) + 1):
            if n % i == 0:
                if simple(i) and simple (n // i):
                    print(n, n // 311)
                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;
begin
    n := 1205500;
    while n mod 311 <> 0 do
        n := n + 1;
    while n <= 12959599 do
    begin
        if n div 100 mod 10 = 5  then
        begin
            z := n div 1000;
            while z > 9999 do
                z := z div 10;
            if (z div 100 = 12) and (z mod 10 = 5) then
                for i := 2 to round(sqrt(n)) do
                    if n mod i = 0 then
                        if simple(i) and simple(n div i) then
                            Writeln(n, ' ', n div 311)
                        else
                            break;
        end;
        n := n + 311;
    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
    n := 1205500;
    while n mod 311 <> 0 do
        n := n + 1;
    while n <= 12959599 do
    begin
        s := IntToStr(n);
        if (s[:3] = '12') and (s[4] = '5') and (s[s.Length - 2] = '5')  then
            for i := 2 to round(sqrt(n)) do
                if n mod i = 0 then
                    if simple(i) and simple(n div i) then
                        Writeln(n, ' ', n div 311)
                    else
                        break;
        n := n + 311;
    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()
{
    int z = 1205500;
    while (z % 311 != 0)
        z++;
    for (int n = z; n < 12959600; n += 311)
    {
        if (n / 100 % 10 == 5)
        {
            int z = n / 1000;
            while (z > 9999)
                z /= 10;
            if (z / 100 == 12 && z % 10 == 5)
            {
                for (int i = 2; i <= sqrt(n); i++)
                    if (n % i == 0)
                        if (simple(i) && simple(n / i))
                            cout << n << " " << n / 311 << 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()
{
    int z = 1205500;
    while (z % 311 != 0)
        z++;
    for (int n = z; n < 12959600; n += 311)
    {
        string s = to_string(n);
        if (s.substr(0, 2) == "12" && s[3] == '5' && s[s.length() - 3] == '5')
        {
            for (int i = 2; i <= sqrt(n); i++)
                if (n % i == 0)
                    if (simple(i) && simple(n / i))
                        cout << n << " " << n / 311 << endl;
                    else
                        break;
        }
    }
}

Ответ

12056537 38767
12153569 39079
12451507 40037
12459593 40063
12655523 40693
12854563 41333

Отправить замечание по решению

Код по которому имеется замечание:

Ваш вариант кода:

Комментарий: