# PBinfo #2175 – Factori – Rezolvare C++

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

## Enunț

Gigel a aflat la matematică definiţia factorialului unui număr natural nenul n. Acesta este produsul tuturor numerelor naturale începând cu 1 şi terminând cu numărul respectiv şi se notează cu n!. Astfel, factorialul numărului natural 6 este 6!=1*2*3*4*5*6 şi este egal cu 720. Factorialele numerelor naturale cresc însă extrem de repede. De exemplu, 7!=5040 în timp ce 10!=3628800.

Fiind un bun matematician, Gigel a imaginat o altă metodă de a indica factorialul unui număr. Astfel, el ştie că un număr natural nenul se poate descompune în factori primi. De exemplu 720 poate fi scris ca 24*32*51.  Gigel codifică descompunerea în factori primi astfel: 4 2 1 însemnând faptul că în descompunerea lui 720 în factori primi apare factorul 2 de 4 ori, factorul 3 apare de două ori şi factorul 5 apare o dată. Cu alte cuvinte, Gigel indică pentru fiecare număr prim ≤ n puterea la care acesta apare în descompunerea în factori primi a lui n!.

Cerința
Scrieţi un program care să citească o secvenţă de numere naturale nenule şi care să afişeze în modul descris în enunţ factorialele numerelor citite.

Date de intrare
Fişierul de intrare factori.in conţine mai multe numere naturale nenule, câte un număr pe linie. Ultima linie a fişierului de intrare conţine valoarea 0 indicând faptul că setul de numere s-a terminat.

Date de ieșire
Fişierul de ieşire factori.out va conţine câte o linie pentru fiecare număr nenul din fişierul de intrare. Pe linia i din fişierul de ieşire va fi descrisă descompunerea în factori primi a factorialului numărului de pe linia i din fişierul de intrare, în modul descris în enunţ. Numerele scrise pe aceeaşi linie vor fi separate prin câte un spaţiu.

Restricții și precizări
Numerele naturale din fişierul de intrare (exceptând ultimul) sunt din intervalul [2, 60000].
Fişierul de intrare conţine maxim 10 numere naturale nenule.

Exemplu:
factori.in

2
8
15
10
0
factori.out

1
7 2 1 1
11 6 3 2 1 1
8 4 2 1
Explicație
2! = 2
8! = 2*2*2*2*2*2*2*3*3*5*7
15! = 2*2*2*2*2*2*2*2*2*2*2*3*3*3*3*3*3*5*5*5*7*7*11*13
10! = 2*2*2*2*2*2*2*2*3*3*3*3*5*5*7

## Cod sursă C++

```cpp
//Marinel Serban
//100 puncte
#include <stdio.h>
#include <math.h>
#define MAX 60001
#define TRUE 1
#define FALSE 0
unsigned long N;
char Prime[MAX];
void TabelPrime(void)
{                                        //Ciurul lui Eratostene
  unsigned long i,j;                     //vectorul Prime va contine
  double Radical;                        //      1 pentru valori prime
                                         //      0 pentru valori neprime
  for (i=1; i<=MAX; i++) Prime[i]=TRUE;
  i=1;
  Radical=sqrt(MAX);
  while (i<=Radical)
	{
	  do
		{
		  i++;
		} while (!Prime[i]);
	  j=i*i;
	  while (j<=MAX)
		{
		  Prime[j]=FALSE;
		  j+=i;
		}
	}
}
int CitesteNumar(void)
{
  scanf("%lu", &N);
  return (N!=0);
}
unsigned long Descompune(unsigned long N, unsigned long d)
{
  unsigned long s;
//  if (N<p)           //varianta recursiva   
//	return 0;
//  else
//	return N/p + Descompune(N/p, p);
  s = 0;               //initializez contorul cu 0
  while (N>=d)         //cat timp d mai poate sa apara
    {
      s = s + N / d;   //d apare de N DIV d ori, le numar
      N = N / d;       //elimin aceste aparitii
    }
  return s;
}
void Rezolva(void)
{
  unsigned long i, j;
  i=2;
  while (!Prime[i]) i++;
  printf("%lu", Descompune(N, i));
  for (j=i+1; j<=N; j++)
	if (Prime[j]) printf(" %lu", Descompune(N,j));
  printf("\n");
}
int main()
{
  freopen("factori.in", "r", stdin);
  freopen("factori.out", "w", stdout);
  TabelPrime();
  while (CitesteNumar()) Rezolva();
  fclose(stdin);
  fclose(stdout);
  return 0;
}
```

## Resurse

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