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 317 este un număr extraprim: el este număr prim şi, în plus, dacă eliminăm cifra 3, obţinem 17, care este prim; dacă eliminăm 1, obţinem 37, care este prim; dacă eliminăm 7, obţinem 31, care este şi el număr prim.

Cerință

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

Date de intrare

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

Date de ieșire

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

Restricții și precizări

• 10 < a ≤ b < 10000000;
• Numărul 1 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ă 4 numere extraprime mai mari decât 10 şi mai mici decât 100: 23, 37, 53 şi 73.

Exemplul 2

input.txt:

99999999999999999999 1

Output:

Input-ul nu convine conditiilor

Rezolvare

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")