Задача 6427. Источник: Поляков. Задание КИМ 25
Назовём маской числа последовательность цифр, в которой также могут встречаться следующие символы:
— символ «?» означает ровно одну произвольную цифру;
— символ «*» означает любую последовательность цифр произвольной длины; в том числе «*» может задавать и пустую последовательность.
Например, маске 123*4?5 соответствуют числа 123405 и 12300425.
Среди натуральных чисел, не превышающих 107, найдите все числа, соответствующие маске 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