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 extraprime.in 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 extraprime.out 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;

Exemplu

extraprime.in

10 100

extraprime.out

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.

Cum e corect?

cout < "As la info"; cout << "As la info"; cout >> "As la info";

Felicitări! Poți mai mult?

Avem sute de probleme pentru tine, fiecare cu explicații ușor de înțeles.

Greșit, dar nu-i bai!

Antrenează-te cu sutele de probleme pe care ți le-am pregătit. Îți explicăm fiecare problemă în parte.

Rezolvare

Iată rezolvarea de 100 de puncte pentru problema Extraprime:

//Serban Marinel - martie 2013
//Gasiti numere prime cu proprietatea ca prin stergerea oricarei cifre
//ramane tot un numar prim
//se citesc a, b
//se cere:
//-a. cate numere prim_de_tot se gasesc in [a, b]
//-b. cel mai mic numar din prim_de_tot din [a, b]
//-c. cel mai mare numar prim_de_tot din [a, b]
//0,1 NU sunt prime
//2 <= a <= b <= 10^7
Program ExtraPrime;

CONST MAX = 10000000;

Var ciur: Array[1..MAX] Of Boolean;
    P: Array[0..8] Of LongInt = (1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000);
    nr, nrmin, nrmax, nrcifre: LongInt;
    Fin, Fout: Text;
    i, j, a, b: LongInt;

Function Verifica(i: LongInt): Boolean;
Var j, t: LongInt;
    v: Boolean;
Begin
    {elimina pe rand cate o cifra si testeaza rezultatul}
    t := 1; v := TRUE;

    While (t < i) AND v Do
    Begin
      { sterge cifra a log_10(t)}
      j := i DIV 10 DIV t * t + i MOD t;
      If NOT ciur[j] Then
        v := FALSE;
      t := t * 10;
    End;
    Verifica := v;
End;

Begin
    Assign(Fin, 'extraprime.in'); Reset(Fin);
    Assign(Fout, 'extraprime.out'); ReWrite(Fout);
    ReadLn(Fin, a, b);
    nrcifre := 1;
    While P[nrcifre] < b Do Inc(nrcifre);
    ciur[1] := FALSE;                 {1 nu este prim}
    For i := 2 To P[nrcifre] Do ciur[i] := TRUE;

    {ciur}
    i := 2;
    While i * i < P[nrcifre] Do
      Begin
        While NOT ciur[i] Do i := i + 1;
        j := i * i;
        While j < P[nrcifre] Do
          Begin
            ciur[j] := FALSE;
            j := j + i
          End;
        i := i + 1
      End;

    nr := 0;
    For i := a To b Do
        If (ciur[i]) AND (verifica(i)) Then
            Begin
                Inc(nr);
                If nr = 1 Then nrmin := i ;
                nrmax := i;
            End;
    WriteLn(fout, nr);
    WriteLn(fout, nrmin);
    WriteLn(fout, nrmax);
    Close(Fout);
End.

Atenție

Enunțurile afișate pe această pagină aparțin exclusiv site-ului PbInfo. Astfel, pentru ștergerea conținutului, puteți să ne contactați la adresa Adresa de email .

Rezolvarea problemei #1145 Extraprime

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #1145 Extraprime de pe PbInfo.ro. Atenție: nu încurajăm copiatul codului! Totuși, credem cu tărie că analizarea unei soluții corecte este o metodă foarte ușoară de a învăța informatică, astfel că oferim sursele pentru peste 1500 de probleme de pe platforma PbInfo.ro.

Pentru rezolvări PbInfo de la peste 1500 de probleme, vă invităm să intrați pe site-ul nostru!

Rezolvare completă PbInfo #1145 Extraprime