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

Liczby względnie pierwsze

SPIS TREŚCI

Problem

W przedziale liczb naturalnych [ a, b  ] należy wyszukać wszystkie liczby względnie pierwsze ( ang. relatively prime integers ) z zadaną liczbą p.


Liczba naturalna m  jest względnie pierwsza ( ang. coprime ) z liczbą naturalną n  wtedy i tylko wtedy, gdy NWD ( m, n  ) = 1. Definicja ta oznacza, iż liczby n  i m  nie posiadają wspólnych podzielników za wyjątkiem 1.

Rozwiązanie

Przechodzimy przez kolejne liczby w przedziale [ a, b  ]. 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, aN.
b  – koniec przedziału, bN.
p  – liczba służąca do wyznaczenia w przedziale [ a, b  ] 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.

Zmienne pomocnicze:

i  –  przebiega przez kolejne liczby w przedziale [ a, b  ]. iN.
t  –   tymczasowo przechowuje dzielnik w algorytmie Euklidesa, tN.
ax  – zmienna dla algorytmu Euklidesa. axN.
bx  – zmienna dla algorytmu Euklidesa. bxN.

Lista kroków:

K01: Dla i  = a, a + 1, ..., b:
wykonuj
kroki K02...K08
przechodzimy przez kolejne liczby z przedziału [ a, b  ]
K02:     ax  ← i zmienne dla algorytmu Euklidesa
K03:     bx  ← p  
K04:     Dopóki bx  ≠ 0,
    wykonuj kroki K05...K07
wyznaczamy NWD ( i, p )
K05:         t  ← bx  
K06:         bx  ← ax mod bx  
K07:         ax  ← t  
K08:     Jeśli ax  = 1,
    to pisz i
NWD ( i, p ) = 1, zatem i jest 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
 
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
Liczby względnie pierwsze
(C)2020 mgr Jerzy Wałaszek

a =
b =
p =


...

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.