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

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

1. Reading input from a file

with open("input.txt", "r") as infile:

   a, b = map(int, infile.readline().split())
   verificare(a,b)

1. 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>