Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Najmniejsza wspólna wielokrotność

SPIS TREŚCI

Problem

Dla danych dwóch liczb naturalnych a  i b  znaleźć najmniejszą liczbę naturalną c, która jest podzielna bez reszty przez a  i przez b.

Liczba naturalna c  o takich własnościach nosi nazwę NWW – najmniejszej wspólnej wielokrotności liczb a i b ( ang. the least common multiple of a  and b  ).

Rozwiązanie

Sposób obliczania NWW jest bardzo prosty:

Jeśli liczby a  i b  są względnie pierwsze, to

Wtedy

Algorytm wyznaczania najmniejszej wspólnej wielokrotności

Wejście:

a, b  –  liczby, których NWW poszukujemy, a, bN.

Wyjście:

NWW – najmniejsza wspólna wielokrotność liczb a  i b.

Zmienne pomocnicze:

ab  –  zapamiętuje iloczyn a  i b. abN.
t  –  tymczasowo przechowuje dzielnik w algorytmie Euklidesa, tN.

Lista kroków:

K01: ab  ← a  × b zapamiętujemy iloczyn a i b
K02: Dopóki b  ≠ 0,
wykonuj
kroki K03...K05
algorytmem Euklidesa znajdujemy NWD ( a, b )
K03:     t  ← b  
K04:     b  ← a  mod b  
K05:     a  ← t  
K06: ab  ← ab  div a obliczamy NWW
K07: Pisz ab  
K08: Zakończ  

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program odczytuje z pierwszego wiersza liczby a  i b. W następnym wierszu wypisuje NWW ( a, b  ). W programie zastosowano zmienne 64 bitowe.
Pascal
// NWW 
// Data   : 2.04.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

program prg;

var a, b, t, ab : qword;

begin
  readln ( a, b );
  ab := a * b;
  while b <> 0 do
  begin
    t := b;
    b := a mod b;
    a := t;
  end;
  ab := ab div a;
  writeln ( ab );
  writeln;
end.
   C++
// NWW
// Data   : 2.04.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

int main( )
{
  unsigned long long a, b, t, ab;

  cin >> a >> b;
  ab = a * b;
  while( b )
  {
    t = b;
    b = a % b;
    a = t;
  }
  ab /= a;
  cout << ab << endl << endl;
  return 0;
}
   Basic
' NWW 
' Data   : 2.04.2008
' (C)2020 mgr Jerzy Wałaszek
'----------------------------

Dim As Ulongint a, b, t, ab

Input a, b
ab = a * b
While b
  t = b
  b = a Mod b
  a = t
Wend
ab = ab \ a
Print ab
Print
End
Wynik:
9 6
18
Najmniejsza Wspólna Wielokrotność
(C)2020 mgr Jerzy Wałaszek

a =
b =


...

Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.
Informacje dodatkowe.