Najmniejsza wspólna wielokrotność


Tematy pokrewne
Przedziały liczbowe i liczby
Liczby parzyste i nieparzyste
Liczby podzielne lub niepodzielne przez zadane podzielniki
Ciągi arytmetyczne
NWD – algorytm Euklidesa
Liczby względnie pierwsze
Najmniejsza wspólna wielokrotność
Odwrotność modulo – rozszerzony algorytm Euklidesa
Liczby pierwsze – generacja przez sprawdzanie podzielności
Liczby pierwsze – generacja sitem Eratostenesa
Liczby pierwsze – generacja sitem liniowym
Liczby pierwsze – generacja sitem Atkina-Bernsteina
Czynniki pierwsze – metoda próbnych dzieleń
Czynniki pierwsze – metoda Fermata
Pierwszość liczby naturalnej – algorytmy naiwne
Pierwszość liczby naturalnej – Chiński Test Pierwszości
Pierwszość liczby naturalnej – Małe Twierdzenie Fermata
Pierwszość liczby naturalnej – test Millera-Rabina
Liniowe generatory liczb pseudolosowych
Generator pseudolosowy Park-Miller
Generator pseudolosowy Mersenne Twister
Wbudowane generatory liczb pseudolosowych
Generowanie liczb pseudolosowych
Liczby Fibonacciego
System liczbowy Fibonacciego
Całkowity pierwiastek kwadratowy

 

Problem

Dla danych 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). Sposób obliczania NWW jest bardzo prosty:

 

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

 

Jeśli liczby a i bwzglę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, a,b N
Wyjście:

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

Zmienne 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 wykonuj kroki K03...K05 ; algorytmem Euklidesa znajdujemy NWD(a,b)
K03:     t b  
K04:     ba mod b  
K05:     at  
K06: abab div a ; obliczamy NWW
K07: Pisz ab  
K08: Zakończ  

 

Program

Ważne:

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.

 

Lazarus Code::Blocks Free Basic
// NWW 
// Data   : 2.04.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

var a,b,t,ab : int64;

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.
// NWW
// Data   : 2.04.2008
// (C)2012 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;
}

 

' NWW 
' Data   : 2.04.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek

a = , b =


...

 



List do administratora Serwisu Edukacyjnego I LO

Twój email: (jeśli chcesz otrzymać odpowiedź)
Temat:
Uwaga: ← tutaj wpisz wyraz  ilo  , inaczej list zostanie zignorowany

Poniżej wpisz swoje uwagi lub pytania dotyczące tego rozdziału (max. 2048 znaków).

Liczba znaków do wykorzystania: 2048

W związku z dużą liczbą listów do naszego serwisu edukacyjnego nie będziemy udzielać odpowiedzi na prośby rozwiązywania zadań, pisania programów zaliczeniowych, przesyłania materiałów czy też tłumaczenia zagadnień szeroko opisywanych w podręcznikach.



   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

(C)2014 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.