Editing 1145 - Extraprime

Gigel, mare amator de probleme de matematică şi informatică, a observat că unele numere prime au o proprietate interesantă: orice cifră ar elimina dintr-un astfel de număr, numărul obţinut este tot număr prim. A numit astfel de numere numere extraprime. De exemplu, numărul <code>317</code> este un număr extraprim: el este număr prim şi, în plus, dacă eliminăm cifra <code>3</code>, obţinem <code>17</code>, care este prim; dacă eliminăm <code>1</code>, obţinem <code>37</code>, care este prim; dacă eliminăm <code>7</code>, obţinem <code>31</code>, care este şi el număr prim.

= Cerință =
Spunem că <code>x</code> este între <code>a</code> şi <code>b</code> dacă <code>x≥a</code> şi <code>x≤b</code>. Fiind date două valori naturale <code>a</code> şi <code>b</code>, să se determine câte numere extraprime există între <code>a</code> şi <code>b</code>, precum şi cel mai mic şi cel mai mare număr extraprim dintre <code>a</code> şi <code>b</code>.

= Date de intrare =
Fișierul de intrare <code>input.txt</code> conține pe prima linie cele două valori naturale <code>a</code> şi <code>b</code>, separate printr-un spaţiu.

= Date de ieșire =
Fișierul de ieșire <code>output.txt</code> va conține <code>3</code> linii. Pe prima linie se va scrie un număr natural <code>nr</code> reprezentând numărul de numere extraprime dintre <code>a</code> şi <code>b</code>. Pe linia a doua a fişierului de ieşire se va scrie cel mai mic număr extraprim dintre <code>a</code> şi <code>b</code>, iar pe linia a treia a fişierului de ieşire se va scrie cel mai mare număr extraprim dintre <code>a</code> şi <code>b</code>.

= Restricții și precizări =

* <code>10 < a ≤ b < 10000000</code>;
* Numărul <code>1</code> nu este prim;
* Pentru datele de test există întotdeauna soluţie;

== Exemplul 1 ==
input.txt:

10 100

output.txt:

4

23

73

Explicație:

Se află <code>4</code> numere extraprime mai mari decât <code>10</code> şi mai mici decât <code>100</code>: <code>23</code>, <code>37</code>, <code>53</code> şi <code>73</code>.

== Exemplul 2 ==
input.txt:

99999999999999999999 1

Output:

Input-ul nu convine conditiilor

== Rezolvare ==
<syntaxhighlight lang="python3" line="1">
from math import log10

def verificare(a, b):
    if not(10<=a<=10000000):
        print("Input-ul nu convine conditiilor")
        exit()
    if not(10<=b<=10000000):
        print("Input-ul nu convine conditiilor")
        exit()

N = 10000000
e = [0] * (N + 1)
fr = [0] * (N + 1)
a, b, t, maxi, mini = 0, 0, 0, -1, N

def ciur():
    e[0] = e[1] = 1

    for i in range(2, N + 1):
        if not e[i]:
            for j in range(i * 2, N + 1, i):
                e[j] = 1

def eliminare(x):
    pow10, get, k = 1, 0, 0

    if e[x]:
        return 0

    while pow10 <= x:
        get = x % pow10
        k = x // pow10 // 10
        k = k * pow10 + get

        if e[k]:
            return 0

        pow10 *= 10

    return 1

ciur()

# Reading input from a file
with open("input.txt", "r") as infile:
    a, b = map(int, infile.readline().split())
    verificare(a,b)

# Writing output to a file
with open("output.txt", "w") as outfile:
    for i in range(a, b + 1):
        r = eliminare(i)
        t += r

        if r == 1:
            maxi = max(maxi, i)
            mini = min(mini, i)

    outfile.write(f"{t}\n{mini}\n{maxi}\n")

</syntaxhighlight>