NWW - najmniejsza wspólna wielokrotność

powrót

Do wyznaczenia najmniejszej wspólnej wielokrotności liczb naturalnych dodatnich $$a$$ i $$b$$ (NWW(a, b)), czyli takiej najmniejszej liczby naturalnej dodatniej, która dzieli się przez $$a$$ i $$b$$ wykorzystamy prosty wzór:

$$NWW(a,b)=\frac{a\cdot b}{NWD(a,b)}$$

gdzie $$NWD(a,b)$$ jest największym wspólnym dzielnikiem liczb $$a$$ i $$b$$. Do wyznaczania NWD służy algorytm Euklidesa, który został opisany w tym miejscu.

W sytuacji, gdy iloczyn liczb  $$a$$ i $$b$$ może przekroczyć zakres danego typu, można wykonać skrócenie:

$$\frac{a}{NWD(a,b)}$$

lub

$$\frac{b}{NWD(a,b)}$$

czyli

$$wynik= \frac{a}{NWD(a,b)}\cdot b$$

Dla przykładu przypiszmy:

• $$ a = 24$$
• $$ b = 36$$

$$NWD(24,36)=12$$

$$NWW(24,36)=24/NWD(24,36)\cdot 36 = 24/12\cdot 36 = 72$$

Liczba $$72$$ jest najmniejszą liczbą naturalną, która dzieli się przez $$24$$ i $$ 36$$.

Rozwiązanie w C++:

//algorytm.edu.pl
#include<iostream>
using namespace std;

int NWD(int a, int b)
{
	int pom;

  	while(b!=0)
	{
    	pom = b;
    	b = a%b;
    	a = pom;  
  	}
    return a;
}

int main()
{
	unsigned int a, b;
	
	cout<<"Podaj dwie liczby: ";
	cin>>a>>b;
	
	//wyznaczenie NWW
	cout<<"NWW("<<a<<", "<<b<<") = "<<a/NWD(a, b)*b<<endl;
	
	cin.ignore();
	cin.get();
	
	return 0;
}