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 2⁴*3²*5¹. 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

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

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

//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;
}

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 #2175 Factori

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