Un număr este prim dacă are exact doi divizori naturali. Prin tăierea unui număr în p părți înțelegem împărțirea acestuia în p numere, fiecare de cel puțin o cifră, astfel încât prin alipirea numerelor obținute de la stânga la dreapta obținem numărul inițial.
De exemplu, dacă împărțim numărul 12045 în două părți avem patru variante de tăiere obținându-se numerele: 1 și 2045; 12 și 045; 120 și 45; 1204 și 5. Dacă îl împărțim în trei părți avem șase variante de tăiere obținându-se numerele 1, 2 și 045; 1, 20 și 45; 1, 204 și 5; 12, 0 și 45; 12, 04 și 5; 120, 4 și 5.
Cerința
Se consideră un șir format din N numere naturale.
1) Determinați cel mai mare număr prim din șirul celor N numere.
Un număr este prim dacă are exact doi divizori naturali. Prin tăierea unui număr în p părți înțelegem împărțirea acestuia în p numere, fiecare de cel puțin o cifră, astfel încât prin alipirea numerelor obținute de la stânga la dreapta obținem numărul inițial.
De exemplu, dacă împărțim numărul 12045 în două părți avem patru variante de tăiere obținându-se numerele: 1 și 2045; 12 și 045; 120 și 45; 1204 și 5. Dacă îl împărțim în trei părți avem șase variante de tăiere obținându-se numerele 1, 2 și 045; 1, 20 și 45; 1, 204 și 5; 12, 0 și 45; 12, 04 și 5; 120, 4 și 5.
Cerința
Se consideră un șir format din N numere naturale.
1) Determinați cel mai mare număr prim din șirul celor N numere.
2) Determinați cel mai mare număr prim dintre cele obținute prin tăierea în două părți a fiecărui număr din șirul celor N.
3) Determinați cel mai mare număr prim dintre cele obținute prin tăierea în trei părți a fiecărui număr din șirul celor N.
Date de intrare
Fișierul de intrare tai.in conține pe prima linie numărul C care poate avea doar valorile 1, 2 sau 3 și reprezintă cerința care urmează a fi rezolvată. Pe a doua linie se găsește N, cu semnificația din enunț, iar pe a treia linie se găsește șirul celor N numere naturale despărțite prin câte un spațiu.
Date de ieșire
Fișierul de ieșire tai.out va conține pe prima linie un număr natural reprezentând răspunsul la cerința specificată.
Restricții și precizări
1 ≤ N ≤ 1000 ≤orice număr din șir≤ 1000000000- Pentru cerințele 2 și 3 se garantează că pentru toate numerele din șir se poate efectua tăierea
- Pentru cerința 1 dacă șirul nu conține numere prime se va afișa
0 - Pentru cerințele 2 și 3 dacă în urma tăierilor nu se obține niciun număr prim, se va afișa
0 - În concurs, pentru rezolvarea fiecărei cerințe s-au obținut 30 de puncte. Pe site se acordă 10 puncte pentru exemple.
Exemplul 1
tai.in
1 5 2 13 21 17 1
tai.out
17
Explicație
Numere prime din șir sunt 2, 13 și 17, iar maximul este 17.
Exemplul 2
tai.in
2 3 23 196 27
tai.out
19
Explicație
Din 23 se obțin două numere 2 și 3, din 196 se pot obține numerele 1 și 96 sau 19 și 6, iar din 27 se obțin numerele 2 și 7. Cel mai mare număr prim care se poate obține este 19.
Exemplul 3
tai.in
3 3 1234 17119 5678
tai.out
71
Explicație
Din numărul 1234 se pot obține numerele: 1, 2, 34 sau 1, 23, 4 sau 12, 3, 4.
Din numărul 17119 se pot obține numerele: 1, 7 și 119 sau 1, 71 și 19 sau 1, 711 și 9 sau 17, 1 și 19 sau 17, 11 și 9.
Din numărul 5678 se pot obține numerele: 5, 6 și 78 sau 5, 67 și 8 sau 56, 7 și 8.
Cel mai mare număr prim care se poate obține este 71.
#include <bits/stdc++.h>
using namespace std;
ifstream cin("tai.in");
ofstream cout("tai.out");
int n , x , cer , rez , maxi , maxi1;
int prim (int n)
{
if(n == 0 || n == 1) return 0;
if(n == 2) return 1;
if(n % 2 == 0) return 0;
for(int i = 3 ; i * i <= n ; i += 2)
if(n % i == 0) return 0;
return 1;
}
void desc(int x)
{
int aux = x , p = 1 , c = 0;
while(x != 0)
{
c = (x % 10) * p + c;
x /= 10;
p *= 10;
if(prim(x))
{
if(x > maxi1 && aux != x) maxi1 = x;
}
if(prim(c))
{
if(c > maxi1 && aux != c) maxi1 = c;
}
}
}
int main()
{
cin >> cer >> n;
for(int i = 1 ; i <= n ; i++)
{
cin >> x;
if(prim(x)) if(x > rez) rez = x;
int aux = x , p = 1 , c = 0;
while(x != 0)
{
c = x % 10 * p + c;
x /= 10;
p *= 10;
desc(x);
if(c != aux)desc(c);
if(prim(x))
{
if(x > maxi && aux != x) maxi = x;
}
if(prim(c))
{
if(c > maxi && aux != c) maxi = c;
}
}
}
if(cer == 1) cout << rez;
else if(cer == 2) cout << maxi;
else cout << maxi1;
}
