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

Liczby względnie pierwsze

SPIS TREŚCI

Problem

W przedziale liczb naturalnych 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 . 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:   axi           ; zmienne dla algorytmu
K03:   bxp           ; Euklidesa
K04:   Dopóki bx ≠ 0:   ; wyznaczamy NWD(i,p)
       wykonuj kroki K05…K07
K05:     t bx
K06:     bxax mod bx
K07:     axt
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 ab i p, a następnie wypisuje wszystkie liczby w przedziale <a,b> względnie pierwsze 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

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
©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.