Cerința

Aky și Alex joacă un joc interesant. Acesta se desfășoară în felul următor: aceștia au cartonașe cu numere naturale până la 10.000.000 (se consideră că au un număr infinit de cartonașe pentru fiecare număr natural mai mic sau egal cu 10.000.000). Ei aleg la întâmplare n cartonașe din cele date, iar pentru fiecare număr x de pe un cartonaș ales caută cartonașul pe care se află scris cel mai mare divizor prim al numărului x.

Astfel observă că pentru multe din numerele alese cel mai mare divizor prim coincide, deci se hotărăsc să creeze mai multe perechi de cartonașe astfel: primul cartonaș al perechii va fi un număr prim, P, care este cel mai mare divizor prim al cel puțin unuia dintre numerele alese, iar numărul C de pe al doilea cartonaș reprezintă pentru câte din numerele din șirul numerelor alese numărul de pe primul cartonaș este cel mai mare divizor prim. De asemenea, perechile sunt ordonate crescător după P.

Cei doi băieți nu se descurcă singuri când numerele de pe cartonașe sunt foarte mari, deci vă roagă pe voi să realizați un program care să realizeze afișarea numarului de perechi formate precum și a acestora pentru un șir de n cartonașe alese.

Date de intrare

Fișierul de intrare jocprim.in conține pe prima linie numărul n, iar pe a doua linie n numere naturale separate prin spații.

Date de ieșire

Fișierul de ieșire jocprim.out va conține pe prima linie numărul de perechi formate, iar pe următoarele linii, câte o pereche de numere P și C, separate printr-un spațiu, cu semnificațiile din enunț.

Restricții și precizări

1 ≤ n ≤ 20000
numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 10.000.000

Exemplu

jocprim.in

12
6 8 3 4 24 20 25 26 30 15 18 22

jocprim.out

Explicație

2 este cel mai mare divizor prim a 2 numere din fișierul de intrare, 3 și 5 a 4 numere, iar 11 și 13 a câte unui număr.

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 jocprim:

#include <bits/stdc++.h>

using namespace std;

#define NN 10000000

ifstream f("jocprim.in");
ofstream g("jocprim.out");

int ciur[NN + 1], v[NN + 1];

int main() {
  //algoritm de tip ciurul lui Eratostene(la final ciur[i] va fi cel mai mare divizor prim al lui i)
  for (int i = 2; i <= NN; i++)
    if (ciur[i] == 0)
  {
    ciur[i] = i;
    for (int j = 2; i * j <= NN; j++)
      ciur[i * j] = i;
  }
  int n, x, i, cnt = 0;
  f >> n;
  while (n--)
  {
    f >> x;
    if (v[ciur[x]] == 0)
      cnt++; //daca v[ciur[x]] este 0, inseamna ca apare o noua pereche
    v[ciur[x]]++; //numarul ciur[x] este cel mai mare divizor prim pentru inca un numar din sir(x)
  }
  g << cnt << '\n'; //afisam numarul de perechi
  for (i = 2; i <= NN; i++) //afisam perechile
    if (v[i]) //daca i este cel mai mare divizor prim pentru cel putin unul din termenii sirului
      g << i << " " << v[i] << '\n'; // afisam i si frecventa acestuia
  f.close();
  g.close();
  return 0;

}

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 #3465 jocprim

Pe această pagină găsești rezolvarea de 100 de puncte pentru problema #3465 jocprim 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 #3465 jocprim