C++ Bc. 42 cpp

Předpokládáme, že funkce rozklad() má být volána opakovaně a aktualizuje si proto pracovní seznam prvočísel (pro N řekněme do řádu desítek milionů to není technický problém). Pro vytvoření statického seznamu prvočísel bychom mohli použít algoritmus známý jako Eratosthenovo síto.

#include <iostream>
#include <vector>

void rozklad(int N, std::vector<int>& prvocisla,
	     std::vector<int>& zaklad, std::vector<int>& mocnina)
{
  zaklad.clear();              // vyprazdnime vystupni parametry
  mocnina.clear();

  int max = prvocisla.back();
  while (max < N)              // podle potreby rozsirime seznam prvocisel
    {
      bool hledej;
      do
	{
	  hledej = false;
	  max += 2;            // kandidat na dalsi prvocislo
	  for (int k=0; k<prvocisla.size(); k++)
	    {
	      int p = prvocisla[k];
	      if (max % p == 0)
		{
		  hledej = true;
		  break;
		}
	      if (p*p > max) break;
	    }
	  if (!hledej)
	    {
	      prvocisla.push_back(max);
	    }
	}
      while (hledej);
    }


  for (int k=0; k<prvocisla.size() && N > 1; k++)
    {
      int exp = 0;
      int p = prvocisla[k];
      while (N%p == 0)
	{
	  N /= p;
	  exp++;
	}

      if (exp > 0)
	{
	  zaklad.push_back(p);
	  mocnina.push_back(exp);
	}
    }
}


int main()
{
  std::vector<int> prvocisla;
  prvocisla.push_back(2);      // vlozime do seznamu prvni dve prvocisla
  prvocisla.push_back(3);

  std::vector<int> p;          // prvocisla rozkladu
  std::vector<int> m;          // mocniny

  for (int n=2; n<=33; n++)
    {
      rozklad(n, prvocisla, p, m);
      std::cout << n << " = ";
      for (int i=0; i<p.size(); i++)
	{
	  if (i != 0) std::cout << " * ";  // symbol nasobeni pro 2. a dalsi cleny
	  std::cout << p[i];
	  if (m[i] > 1) std::cout << "^" << m[i]; // mocniny 1 netiskneme
	}
      std::cout << "\n";
    }
}

Verze idioten sicher und bomben fest (například pro testováni a pod.)

#include <iostream>
#include <vector>

void rozklad(int N, std::vector<int>& zaklad, std::vector<int>& mocnina)
{
  zaklad.clear();  // vyprazdnim vystupni parametry
  mocnina.clear();

  for (int i=2; i<=N; i++) 
    {
      int exp = 0;
      while (N%i == 0) // cislo N je delitelne i 
	{
	  N /= i; 
	  exp++;
	}
      if (exp != 0)
	{
	  zaklad.push_back(i);
	  mocnina.push_back(exp);
	}
    }
  
  if (zaklad.size() == 0) // N je prvocislo
    {
      zaklad.push_back(N);
      mocnina.push_back(1);
    }
}


int main()
{
  std::vector<int> p;  // prvocisla rozkladu
  std::vector<int> m;  // mocniny

  for (int n=2; n<=33; n++)
    {
      rozklad(n, p, m);
      std::cout << n << " = ";
      for (int i=0; i<p.size(); i++)
	{
	  if (i != 0) std::cout << " * ";  // symbol nasobeni pro 2. a dalci cleny
	  std::cout << p[i] << "^" << m[i];
	}
      std::cout << "\n";
    }
}

[ Zpět ]