Question

Ma ajuta si pe mine cineva cu problema 3314 de pe pbinfo? Cerința Se dau n numere naturale nenule. Aflaţi pentru fiecare număr dat x, câte numere naturale nenule mai mici sau egale cu x sunt prime cu x? Date de intrare Fișierul de intrare eratostene3.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 eratostene3.out va conține pentru fiecare număr x din fişierul de intrare, numărul de numere naturale nenule mai mici sau egale cu x, prime cu x. Restricții și precizări 1 ≤ n ≤ 100.000 numerele de pe a doua linie a fișierului de intrare vor fi mai mici decât 1.000.000 Exemplu eratostene3.in 3 4 7 12 eratostene3.out 2 6 4 Explicație

Answer 1

Răspuns:

#include <iostream>

#include <fstream>

using namespace std;

ifstream fin ("eratostene3.in");

ofstream fout ("eratostene3.out");

int main()

{

int n, x, y, C, cx;

fin >> n;

for (int i = 1; i <= n; i++)

{

 fin >> x;

 C = 0;

 for (int j = 1; j <= x; j++)

 {

  y = j;

  cx = x;

  while (y != cx)

  {

   if (cx>y)

    cx = cx - y;

   else y = y - cx;

  }

  if (y == 1)

   C++;

 }

 fout << C;

}

       fin.close();

       fout.close();

return 0;

}

Explicație:

Dupa fiecare numar citit in variabila x, contorul C (care contorizeaza cate numere mai mici sau egale cu x sunt prime cu acesta) este 0. Parcurgem toate numerele mai mici sau egale cu x (adica de la 1 la x) cu variabila j, dar pentru a nu pierde valorile memorate in variabilele x si j, le memoram in alte variabile, si anume cx si y. Astfel, cx memoreaza valoarea lui x, iar y memoreaza valoarea lui j. Structura "while" care urmeaza dupa asta calculeaza cmmdc al celor 2 numere, iar dupa ce iesim din "while", y si cx o sa fie egale, ambele memorand cmmdc al numerelor x si j, care ne intereseaza. Daca y (sau cx) este 1, inseamna ca numerele sunt prime intre ele, deci prin urmare, contorul (adica C) se mareste cu 1. Repetam aceeasi procedura pentru celelalte numere din intervalul [1;x], iar la final il afisam pe C. Dupa asta, citim inca un numar x si procedam la fel ca pana acum.

Daca ai nelamuriri, nu ezita sa mi le comunici. :)