Algorytmy i Struktury Danych - Liczby względnie pierwsze

Przechodzimy przez kolejne liczby w przedziale . Dla każdej liczby obliczamy algorytmem Euklidesa jej NWD z liczbą p. Jeśli wynikiem będzie 1, to obie liczby są względnie pierwsze, zatem wyprowadzamy tę liczbę z przedziału na wyjście.

Algorytm wyznaczania liczb względnie pierwszych

Wejście:

a : początek przedziału; a ∈ N.
b : koniec przedziału; b ∈ N.
p : liczba służąca do wyznaczenia w przedziale liczb z nią względnie pierwszych; p ∈ N.

Wyjście:

liczby z przedziału <a, b>, które są względnie pierwsze z liczbą p.

Elementy pomocnicze:

i : przebiega przez kolejne liczby w przedziale <a, b>; i ∈ N.
t : tymczasowo przechowuje dzielnik w algorytmie Euklidesa; t ∈ N.
ax : zmienna dla algorytmu Euklidesa; ax ∈ N.
bx : zmienna dla algorytmu Euklidesa; bx ∈ N.

Lista kroków:

K01: Dla i = a, a+1, …, b: ; przechodzimy przez kolejne
     wykonuj kroki K02…K08 ; liczby z przedziału
K02:   ax ← i ; zmienne dla algorytmu
K03:   bx ← p ; Euklidesa
K04:   Dopóki bx ≠ 0: ; wyznaczamy NWD(i, p)
       wykonuj kroki K05…K07
K05:     t ← bx
K06:     bx ← ax mod bx
K07:     ax ← t
K08:   Jeśli ax = 1, ; NWD(i, p) = 1, zatem i jest
       to pisz i ; względnie pierwsze z p
K09: 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 trzy liczby a, b i p, a następnie wypisuje wszystkie liczby w przedziale <a, b> względnie pierwsze z p.

Pascal

// Liczby względnie pierwsze
// Data: 14.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

program prg;

var a, b, p, ax, bx, i, t : cardinal;

begin
  readln(a, b, p);
  for i := a to b do
  begin
    ax := i; bx := p;
    while bx <> 0 do
    begin
      t  := bx;
      bx := ax mod bx;
      ax := t;
    end;
    if ax = 1 then
      write(i, ' ');
  end;
  writeln;
end.

C++

// Liczby względnie pierwsze
// Data: 14.03.2008
// (C)2020 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

int main()
{
  unsigned int a, b, p, ax, bx, i, t;

  cin >> a >> b >> p;
  for(i = a; i <= b; i++)
  {
    ax = i; bx = p;
    while(bx)
    {
      t  = bx;
      bx = ax%bx;
      ax = t;
    }
    if(ax == 1)
      cout << i << " ";
  }
  cout << endl;
  return 0;
}

Basic

' Liczby względnie pierwsze
' Data: 14.03.2008
' (C)2020 mgr Jerzy Wałaszek
'----------------------------

Dim As Uinteger a, b, p, ax, bx, i, t

Input a, b, p
For i = a To b
  ax = i: bx = p
  While bx
    t  = bx
    bx = ax Mod bx
    ax = t
  Wend
  If ax = 1 Then _
    Print i;" ";
Next
Print
End

Python (dodatek)

# Liczby względnie pierwsze
# Data: 04.02.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

arr = input().split()
a = int(arr[0])
b = int(arr[1])
p = int(arr[2])
for i in range(a, b+1):
    ax = i
    bx = p
    while bx:
        t = bx
        bx = ax%bx
        ax = t
    if ax: print(i, end=" ")
print()

Wynik:

1 100 60
1 7 11 13 17 19 23 29 31 37 41 43 47 49 53 59 61 67 71 73 77 79 83 89 91 97

JavaScript

<html>
  <head>
    <title>
      Liczby względnie pierwsze
    </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>Liczby względnie pierwsze</b>
          <br/>
          (C)2026 mgr Jerzy Wałaszek
          <hr>
          a = <input
              type="text"
              name="inp_a"
              size="16"
              value="1"
              style="text-align:
                     right">
          <br>
          b = <input
              type="text"
              name="inp_b"
              size="16"
              value="100"
              style="text-align:
                     right">
          <br>
          p = <input
              type="text"
              name="inp_p"
              size="16"
              value="60"
              style="text-align:
                     right">
          <hr>
          <input
          type="button"
          value="Wykonaj"
          name="B"
          onclick="main()">
          <hr>
          <b>Wynik:</b>
          <div id="out">.</div>
        </form>
      </td>
    </tr>
  </table>
</div>

<script type=text/javascript
        language=javascript>

// Liczby względnie pierwsze
// Data   : 14.03.2008
// (C)2008 mgr Jerzy Wałaszek
//---------------------------

function main ( )
{
  var a,b,c,p,ax,bx,i,t,s;

  a = parseInt(document.frm
      .inp_a.value);
  b = parseInt(document.frm
      .inp_b.value);
  c = 0;
  p = parseInt(document.frm
      .inp_p.value);
  if(!isNaN(a) && !isNaN(b) &&
     !isNaN(p))
  {
    s = "";
    for(i = a; i <= b; i++)
    {
      ax = i; bx = p;
      while(bx)
      {
        t  = bx;
        bx = ax % bx;
        ax = t;
      }
      if(ax == 1)
      {
        s += i + " ";
        c++;
        if(c == 10)
        {
          c = 0;
          s += "<br/>";
        }
      }
    }
  }
  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.

Liczby względnie pierwsze