Rezolvare PBinfo #4343

Numerele naturale nenule x și y se numesc prietene dacă au același număr de divizori primi.

Cerința

Fiind date două șiruri de numere naturale, primul cu n numere, iar al doilea cu m numere, scrieți un program care rezolvă următoarele cerințe:
1) Determină cel mai mare dintre cele n + m numere date ce are număr maxim de divizori primi.
2) Determină câte perechi de numere prietene de forma (x, y) se pot forma, x fiind din primul șir, iar y din al doilea șir.

Date de intrare

Fișierul de intrare prietene.in conţine pe prima linie numărul C reprezentând cerința (1 sau 2), pe a doua linie numerele n și m, pe a treia linie un șir de n numere, iar pe a patra linie un șir de m numere, numerele de pe fiecare linie fiind separate prin câte un spațiu.

Date de ieșire

Dacă C = 1, atunci pe prima linie a fişierului de ieşire prietene.out se va scrie numărul ce reprezintă răspunsul la cerința 1.
Dacă C = 2, atunci pe prima linie a fişierului de ieşire prietene.out se va scrie numărul ce reprezintă răspunsul la cerința 2.

Restricții și precizări

• 1 ≤ n,m ≤ 10.000
• Cele două șiruri conțin numere naturale din intervalul [2, 1.000.000.000].
• Pentru 30% din teste cerinţa va fi C = 1.
• 10 puncte se acordă pentru exemplele din enunț.

Exemplul 1:

prietene.in

1
3 4
36 30 5
12 60 13 77

prietene.out

60

Explicație

Pentru fiecare număr din șirurile date scriem numărul de divizori primi: 36 → 2, 30 → 3, 5 → 1, 12 → 2, 60 → 3, 13 → 1, 77 → 2. Numărul maxim de divizori primi este 3. Cel mai mare număr din șirurile date care are 3 divizori primi este 60.

Exemplul 2:

prietene.in

2
4 5
36 30 5 10
12 60 15 77 105

prietene.out

8

Explicație

Sunt 8 perechi de numere prietene: (36, 12), (36, 15), (36, 77), (10, 12), (10, 15), (10, 77), (30, 60), (30, 105).