Liczby względnie pierwsze


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

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

 

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

program prg;

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

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.
Code::Blocks
// Liczby względnie pierwsze
// Data   : 14.03.2008
// (C)2012 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;
}
Free Basic
' Liczby względnie pierwsze
' Data   : 14.03.2008
' (C)2012 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)2012 mgr Jerzy Wałaszek

a = , b = , p =


...

 



List do administratora Serwisu Edukacyjnego Nauczycieli 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

©2017 mgr Jerzy Wałaszek

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