Se dă un șir de n
cifre. Șirul se împarte în secvențe disjuncte de cifre, fiecare secvență având lungimea cel mult 6
. Cu fiecare secvență extrasă se formează numărul corespunzător și apoi se adună doar numerele prime obținute. De exemplu, dacă șirul de cifre este 37237
, se pot extrage secvențele disjuncte 3
, 72
, 37
, iar suma numerelor prime este 3 + 37 = 40
. O altă modalitate este 3
, 7237
care are suma 7240
(deoarece numărul 7237
este prim).
Cerința
Să se determine suma maximă care se poate obține împărțind șirul în secvențe disjuncte de lungimi cel mult 6
și adunând apoi numai numerele prime.
Date de intrare
Programul citește de la tastatură șirul de cifre, fără spații.
Date de ieșire
Programul va afișa pe ecran suma maximă obținută.
Restricții și precizări
1 ≤ lungimea șirului de cifre ≤ 100.000
- Dacă din șir nu se pot obține numere prime suma va fi
0
.
Exemplul 1:
Intrare
37237
Ieșire
7240
Exemplul 2:
Intrare
44688
Ieșire
0
Exemplul 3:
Intrare
1234577
Ieșire
123464
Explicație
Numărul 1234577
este prim, dar nu poate fi luat ca o singură secvență deoarece are mai mult de 6
cifre. Suma maximă este 123457 + 7 = 123464
.