# PBinfo #3314 – eratostene3 – Rezolvare C++

Sursa: Codul lui Andrei
Limbaj: C++
Autor rezolvare: andrei

## Enunț

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
Numerele prime cu 4, mai mici sau egale cu 4, sunt: 1,3.
Numerele prime cu 7, mai mici sau egale cu 7, sunt: 1,2,3,4,5,6.
Numerele prime cu 12, mai mici sau egale cu 12, sunt: 1,5,7,11.
Vezi Indicatorul lui Euler.

## Cod sursă C++

```cpp
#include <fstream>
using namespace std;
ifstream cin("eratostene3.in");
ofstream cout("eratostene3.out");
int F[1000001];
int main() {
	int Q; cin >> Q;
	for (int i = 1; i <= 1000000; i++) F[i] = i;
	for (int i = 2;  i <= 1000000; i++)
		if (F[i] == i) {
			F[i]--;
			for (int j = 2; j * i <= 1000000; j++)
				F[j * i]= F[j * i] / i * (i - 1);
		}
	for (int q = 1; q <= Q; ++q) {
		int temp; cin >> temp;
		cout << F[temp] << " ";
	} return 0;
}
```

## Resurse

- [Pagina originală](https://codulluiandrei.ro/rezolvari/pbinfo/3314)
- [Sursa C++](https://codulluiandrei.ro/rezolvari/pbinfo/3314/cod.cpp)
- [Sursa pe GitHub](https://raw.githubusercontent.com/codulluiandrei/pbinfo/main/pbinfo-3314/main.cpp)
- [Cursuri de informatică pentru BAC](https://codulluiandrei.ro/academia/info-curs/pachet-cpp/)