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

©2024 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:

NWW(a,b) = (a×b)/ NWD(a,b)

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

NWD(a,b) = 1

Wtedy

NWW(a,b) = a×b

Algorytm wyznaczania najmniejszej wspólnej wielokrotności

Wejście:

a, b : liczby, których NWW poszukujemy; ab ∈ N.

Wyjście:

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

Elementy pomocnicze:

ab : zapamiętuje iloczyn a i b; ab ∈ N.
t : tymczasowo przechowuje dzielnik w algorytmie Euklidesa; t ∈ N.

Lista kroków:

K01: aba×b ; zapamiętujemy iloczyn a i b
K02: Dopóki b ≠ 0: ; algorytmem Euklidesa znajdujemy NWD(a,b)
     wykonuj kroki K03…K05
K03:   tb
K04:   ba mod b
K05:   at
K06: abab 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(ab). 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
Python (dodatek)
# NWW
# Data : 5.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

arr = input().split(" ")
a = int(arr[0])
b = int(arr[1])
ab = a*b
while b:
    t = b
    b = a%b
    a = t
ab //= a
print(ab)
print()
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
©2024 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.