Algorytmy i Struktury Danych - NWW - najmniejsza wspólna wielokrotność

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; a, b ∈ 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: ab ← a×b ; zapamiętujemy iloczyn a i b
K02: Dopóki b ≠ 0: ; algorytmem Euklidesa znajdujemy NWD(a, b)
     wykonuj kroki K03…K05
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

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

JavaScript

<html>
  <head>
    <title>
      Najmniejsza
      Wspólna
      Wielokrotność
    </title>
  </head>
  <body>
<div style="overflow-x: auto;"
     align="center">
  <table
  border="0"
  cellpadding="4"
  style="border-collapse:
         collapse">
    <tr>
      <td nowrap>
        <form
        name="frm"
        style="text-align: center;
               background-color:
               #E7E7DA">
          <b>
          &nbsp;&nbsp;
          Najmniejsza Wspólna
          Wielokrotność
          &nbsp;&nbsp;
          </b><br/>
          (C)2026 mgr Jerzy
          Wałaszek
          <hr>
          a = <input
              type="text"
              name="inp_a"
              size="16"
              value="9"
              style="text-align:
                     right">
          <br>
          b = <input
              type="text"
              name="inp_b"
              size="16"
              value="6"
              style="text-align:
                    right">
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B1"
          onclick="main()">
          <hr>
          <b>Wynik:</b>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

// NWW
// Data   : 2.04.2008
// (C)2008 mgr Jerzy Wałaszek
//---------------------------

function main()
{
  var a,b,t,ab,s;

  a = parseInt(document.frm
      .inp_a.value);
  b = parseInt(document.frm
      .inp_b.value);
  if(!isNaN(a) && !isNaN(b))
  {
    ab = a * b;
    while(b)
    {
      t = b;
      b = a % b;
      a = t;
    }
    s = ab / a;
  }
  else
    s = "Złe dane wejściowe!";
  document.getElementById("out")
  .innerHTML = s;
}

</script>

  </body>
</html>

do podrozdziału do strony

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.

Najmniejsza wspólna wielokrotność