NWD w C++

A) Zaimplementować algorytm (tzn. napisać kod źródłowy, skompilować i uruchomić odpowiedni
program) tworzący tablicę wszystkich liczb pierwszych mniejszych od 9999 i wykorzystujący
„sito Eratostenesa”. UWAGA: Liczb tych jest 1229.

B) Zaimplementować „zbrodniczy” algorytm wyznaczania największego wspólnego dzielnika
dwóch liczb naturalnych (polegający na rozkładzie obu liczb niezależnie na czynniki pierwsze,
a następnie pomnożeniu przez siebie wszystkich wspólnych czynników tych liczb).
„Wbudować” w algorytm mechanizmy zliczania wykonanych podczas realizacji obliczeń
dzieleń każdej z tych liczb przez liczby pierwsze będące elementami tablicy utworzonej
w punkcie A. Założyć, że liczby te nie będą przekraczały wartości 9999, lecz będą większe
od 999 (co oznacza czterocyfrową reprezentację tych liczb w systemie dziesiętnym. UWAGA:
Przy takim założeniu liczba czynników pierwszych dla każdej z liczb nie przekroczy 13-tu.

A więc wszystko mam, tylko nie rozumiem tego zdania

„Wbudować” w algorytm mechanizmy zliczania wykonanych podczas realizacji obliczeń
dzieleń każdej z tych liczb przez liczby pierwsze będące elementami tablicy utworzonej
w punkcie A.
i nie mogę przez to pójść dalej, czy jest ktoś w stanie pomóc?

#define MAX 9999
#include <iostream>
#include <cstdlib>
#include <ctime>
#include <stdlib.h>
using namespace std;
bool tab[MAX];
int licznik_operacji=0, wybor;
int a,b=0;

void menu()
{
   do {
   cout << "Co wybierasz?"
   "\n 1. Sito Eratostenesa" <<
   "\n 2. NWD " << endl;

   cin >> wybor;

   cout << "Twoj wybor to " << wybor << endl;
   cout << endl;

       } while (wybor!=1 && wybor!=2 && wybor!=3);
}

void sitoEratostenesa()
{

    for (int i=2;i<=MAX;i++)
    tab[i]=true;
    for (int i=2;i<=MAX;i++)
    {
    int w = i+i;
         while (w<=MAX)
         {
         tab[w]=false; w+=i;
         }
    }
}
void wyswietlanieTablicy()
{
 for(int i=2;i<=MAX;i++)
 {
  if(tab[i])
  {
   licznik_operacji++;
   cout << i << "\t" << "\t";
  }
 }
}

int NWD(int a, int b)
{
    while(a != b)
    {
        licznik_operacji++;
        if(a > b)
        a = a - b;
        else
        b = b - a;
    }
}

void licznik()
{
   cout << endl;
   cout << "Licznik operacji: " << licznik_operacji << endl;
}

void wybierz()
{
   switch(wybor)
   {
      case 1:
      {
         sitoEratostenesa();
         wyswietlanieTablicy();
         licznik();
         break;
      }
      case 2:
      {
       cout << "Podaj dwie liczby" << endl;
       cout << "Podaj a: ";
       cin >> a;
       cout << "Podaj b: ";
       cin >> b;
       cout << "Najwiekszy wspolny dzielnik ("<<a<<","<<b<<") = " <<NWD(a,b)<<endl;
       break;
      }
   }
}

int main()
{
menu();
wybierz();
system("pause");
return 0;
}

tez nie rozumiem tego. Ale jezeli to Cie zatrzymuje przed robieniem dalej. To na razie opusc to, zostaw sobie na to miejsce (np funkcje ktora bedzie to robic) tak wiec bedziesz wywolywaj pusta funkcje "zliczajOperacje()" w swoim algorytmie. Dzieki temu nie musisz stac ze swoim zadaniem. Jak sie dowiesz o co tam chodzilo, to po prostu to zaimplementujesz w tej funkcji a reszty nie bedziesz musial zmieniac.

int NWD(int a, int b)
{
while(a != b)
{
licznik_operacji++;
if(a > b)
a = a - b;
else
b = b - a;
}
}

Z tego co widzę to Ty używasz tutaj algorytmu euklidesa, a w poleceniu podano Ci, że masz każdą z tych liczb rozłożyć z osobna na czynniki pierwsze, a potem pomnożyć wspólne.

Ok, w takim razie mam tak:

int czynniki()
{
    for (int i=1; i<=2; i++)
    {
        dzielnik=2;
        cout << "Podaj liczby, ktore nalezy rozlozyc na czynniki pierwsze\n";
        cin >> a;

        while(a>1)
        {
            while(a%dzielnik==0)
            {
                cout << "Dzielniki liczby " << a << ": " << dzielnik << endl;
                a/=dzielnik;
            }
            ++dzielnik;
        }
    }
}
 

Jak ma teraz niby mnożyć wszystkie wspólne czynniki? No i co potem?

A ten wiersz z zadania czytałeś: - "Przy takim założeniu liczba czynników pierwszych dla każdej z liczb nie przekroczy 13-tu."

No właśnie nie za bardzo rozumiem tego całego podpunktu, więc jeżeli możesz mi go wyjaśnić to bardzo bym prosił. :)

Może wypisz z tego podpunktu wszystkie słowa których nie rozumiesz lub napisz czego konkretnie nie rozumiesz.

Pierwsze rozwiązanie jakie nasuwa się na myśl to takie żeby rozkładając liczbę na czynniki pierwsze zapisywać je w tablicy. Potem tak samo z drugą i porównać elementy dwóch utworzynych tablic. Natomiast co do

Wbudować” w algorytm mechanizmy zliczania wykonanych podczas realizacji obliczeń
dzieleń każdej z tych liczb przez liczby pierwsze będące elementami tablicy utworzonej
w punkcie A.

W tym swoim algorytmie szukania NWD musisz teraz zliczyć ile razy dzielisz przez liczbę pierwszą ( przeszukując tablicę sita, którą utworzyłeś w punkcie A) )