TAKMIČENJA IZ PROGRAMIRANJA


Sva pitanja, predloge ili primedbe u vezi sa takmičenjima iz programiranja možete slati na e-mail:

tak.prog@gmail.com

U toku perioda za žalbe, sve žalbe možete slati na ovaj isti e-mail.

faktorisanje.cpp    906 b      izvorni kod rešenja
faktorisanje.pas    1,095 b      izvorni kod rešenja
faktorisanje.tests.7z    2,748,996 b      test primeri

zadatak: Faktorisanje

Dato je n brojeva. Potrebno je faktorisati svaki broj, tj. napisati ga kao proizvod prostih činioca. Svaki broj faktorisati u formatu p1^a1 * p2^a2 * ... * pk^ak , gde su p1 ≤ p2 ≤ ... ≤ pk svi prosti činioci datog broja (u rastućem redosledu), a a1, a2, ..., ak - njihovi odgovarajući izložioci. Izmedju brojeva i simbola '*' i '^' ne sme biti razmaka.

Ulaz.

(Ulazni podaci se učitavaju sa standardnog ulaza.) U prvom redu standradnog ulaza nalazi se prirodan broj n ≤ 200.000. U sledećih n redova se nalazi po jedan ceo broj bi koga treba faktorisati (2 ≤ bi ≤ 200.000).

Izlaz.

(Izlazne podatke ispisati na standardan izlaz.) Na standardni izlaz za svaki broj ispisati u posebnom redu njegovu faktorizaciju u gore opisanom formatu, u redosledu datim na ulazu.

Ograničenja.

U 40% test primera n ≤ 1.000

Primer 1.

standardni ulaz      standardni izlaz
3
10
23
180 
        
2^1*5^1
23^1
2^2*3^2*5^1
fajl: faktorisanje.cpp
#include <cstdlib>
#include <cstdio>

const int MaxN = 200010;
const int MaxNum = 200000;

int n, num, p, exp, a[MaxN], leastDiv[MaxNum + 10];
bool prime[MaxNum + 10];

void eratosten(int N, bool prime[], int leastDiv[]) {
  
  for (int i = 0; i <= N; i++) 
      prime[i] = true;
    
  for (int i = 2; i <= N; i++) {
    if (prime[i]) {
      leastDiv[i] = i;
      for (int j = 2; i * j <= N; j++) 
        if (prime[i * j]) {
          prime[i * j] = false;
          leastDiv[i * j] = i;
        }
    }
  }
}

int main() {

  scanf("%d", &n);
  for (int i = 0; i < n; i++)
    scanf("%d", &a[i]);

  eratosten(MaxNum, prime, leastDiv);

  for (int i = 0; i < n; i++) {
    num = a[i];

    while (num > 1) {
      p = leastDiv[num];
      exp = 0;
      while (num % p == 0) {
        exp++;
        num /= p;
      }
      if (num > 1) printf("%d^%d*", p, exp);
      else printf("%d^%d\n", p, exp);
    }
  }

  return 0;
}
fajl: faktorisanje.pas
const
  MaxN = 200010;
  MaxNum = 200000;

var
  n, num, p, exp, i : longint;
  a : array[0..MaxN] of longint;
  leastDiv : array[0..MaxNum + 10] of longint;
  prime : array[0..MaxNum + 10] of boolean;


procedure eratosten(N : longint);
var
  i, j : longint;

begin

  for i := 0 to N do
      prime[i] := true;

  for i := 2 to N do
      if (prime[i]) then begin
          leastDiv[i] := i;
          for j := 2 to N div i do
              if (prime[i * j]) then begin
                  prime[i * j] := false;
                  leastDiv[i * j] := i;
              end;
      end;

end;


begin

  readln(n);
  for i := 1 to n do
      readln(a[i]);

  eratosten(MaxNum);

  for i := 1 to n do begin

      num := a[i];
      while (num > 1) do begin
          p := leastDiv[num];
          exp := 0;
          while (num mod p = 0) do begin
              exp := exp + 1;
              num := num div p;
          end;

          if (num > 1) then write(p, '^', exp, '*')
          else writeln(p, '^', exp);
      end;

  end;

end.