Liczby podzielne lub niepodzielne przez zadane podzielniki


Tematy pokrewne   Podrozdziały
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 1
    Rozwiązanie alternatywne
Problem 2
Problem 3

 

Problem nr 1

W przedziale <a,b> liczb całkowitych wyszukać wszystkie liczby podzielne przez jedną z liczb z zadanego zbioru P.

 

 

W przypadku ogólnym stosujemy podejście pierwsze, czyli generujemy wszystkie kolejne liczby z przedziału <a,b> i sprawdzamy, czy dzielą się bez reszty przez jedną z liczb z zadanego zbioru. Jeśli tak, wyprowadzamy je na wyjście.

 

Algorytm wyznaczania liczb podzielnych przez zadane czynniki

Wejście
a     początek przedziału, a Z
b  – koniec przedziału, b Z, a < b
n  – liczba podzielników,  n N
P  – tablica, której kolejne elementy są podzielnikami. Elementy Z. Numeracja elementów od zera.
Wyjście:

Kolejne liczby z przedziału <a,b> podzielne przez jeden z podzielników w P

Zmienne pomocnicze

i – przebiega przez kolejne liczby w przedziale <a,b>,  i Z
j – przebiega przez numery kolejnych podzielników w Pj N

Lista kroków:
K01: Dla i = a,a+1,...,b wykonuj K02...K03 ; przechodzimy przez kolejne liczby z przedziału <a,b>
K02:     Dla j = 0,1,...,n-1 wykonuj K03 ; sprawdzamy, czy liczba i dzieli się przez jeden z podzielników
K03:         Jeśli i mod P[j] = 0, to:
            pisz i
            następny obieg pętli K01
; z tablicy P[]. Jeśli tak, wyprowadzamy i, przerywamy pętlę K02
K04: 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 spodziewa się w pierwszym wierszu liczb a i b. W drugim wierszu należy podać n = 1...1000, a następnie w n wierszach kolejne podzielniki (nie muszą być uporządkowane).

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

 

-100 100
3
5
12
17

Lazarus
// Liczby podzielne
// Data   : 11.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

const MAXP = 1000;

var a,b,i,j,n : longint;
    P : array[0..MAXP-1] of longint;

begin
  readln(a,b);
  readln(n);
  for i := 0 to n - 1 do
    readln(P[i]);
  for i := a to b do
    for j := 0 to n - 1 do
      if i mod P[j] = 0 then
      begin
        write(i,' ');
        break;
      end;
  writeln;
end.
Code::Blocks
// Liczby podzielne
// Data   : 11.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

const int MAXP = 1000;

int main()
{
  int a,b,i,j,n,P[MAXP];

  cin >> a >> b >> n;
  for(i = 0; i < n; i++)
    cin >> P[i];

  for(i = a; i <= b; i++)
    for(j = 0; j < n; j++)
      if(i % P[j] == 0)
      {
        cout << i << " ";
        break;
      }
  cout << endl;
  return 0;
}
Free Basic
' Liczby podzielne
' Data   : 11.03.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Const MAXP = 1000

Dim As Integer a,b,i,j,n,P(MAXP-1)

Input a,b
Input n
For i = 0 To n - 1
  Input P(i)
Next
For i = a To b
  For j = 0 To n - 1
    If i Mod P(j) = 0 Then
      Print i;" ";
      Exit For
    End If
  Next
Next
Print
End
Wynik
-100 100
3
5
12
17
-100 -96 -95 -90 -85 -84 -80 -75 -72 -70 -68 -65 -60 -55 -51 -50 -48 -45 -40 -36
 -35 -34 -30 -25 -24 -20 -17 -15 -12 -10 -5 0 5 10 12 15 17 20 24 25 30 34 35 36
40 45 48 50 51 55 60 65 68 70 72 75 80 84 85 90 95 96 100

 

Liczby podzielne
(C)2012 mgr Jerzy Wałaszek

a = , b = dzielniki =


...

 

Rozwiązanie alternatywne

Problem można rozwiązać podejściem drugim, tzn. wyznaczając kolejne liczby podzielne przez jeden z podzielników z tablicy P[]. Wystarczy zauważyć, iż liczby te będą wielokrotnościami swoich podzielników. Zatem dla każdego podzielnika wyznaczamy najmniejszą wielokrotność zawartą w przedziale <a,b>. Następnie z tych wielokrotności wybieramy najmniejszą i przesyłamy na wyjście. Jeśli w trakcie szukania najmniejszej liczby trafimy na taką, która została już wysłana na wyjście, to zamieniamy ją na jej następną wielokrotność. Operację kontynuujemy dotąd, aż najmniejsza liczba przekroczy kraniec b przedziału. Poniżej przedstawiamy szczegółowy algorytm tego rozwiązania.

 

Algorytm wyznaczania liczb podzielnych przez zadane czynniki

Wejście
a     początek przedziału, a Z
b  – koniec przedziału, b Z
n  – liczba podzielników,  n N
P  – tablica, której kolejne elementy są podzielnikami. Elementy Z. Numeracja elementów od zera.
Wyjście:

Kolejne liczby z przedziału <a,b> podzielne przez jeden z podzielników w P

Zmienne pomocnicze
i    przebiega przez indeksy podzielników w P[]. i Z
s  – liczba przesłana na wyjście, s Z
minv  – minimalna wartość wielokrotności podzielników z P[]. minv Z
V  – tablica wielokrotności podzielników. Elementy Z. Numeracja elementów od zera zgodna z numeracją P.
MAXZ  – największa wartość całkowita
Lista kroków:
K01: Dla i = 0,1,...,n-1 wykonuj kroki K02...K03  
K02:     Jeśli P[i] < 0, to P[i] ← -P[i] ; ujemne podzielniki zamieniamy na dodatnie
K03:     Jeśli a < 0, to V[i] ← (a div P[i]) × P[i]
    inaczej          V[i] ← ((a + P[i] - 1) div P[i]) × P[i]
; wyznaczamy pierwszą w <a,b> wielokrotność
; podzielnika P[i]
K04: sa - 1 ; s zapamiętuje wysłaną na wyjście liczbę. Nadajemy mu wartość niemożliwą
K05:     minv ← MAXZ ; wśród wielokrotności V szukamy najmniejszej
K06:     Dla i = 0,1,...,n-1 wykonuj kroki K07...K08  
K07:         Jeśli V[i] = s, to V[i] ← V[i] + P[i] ; jeśli trafimy na wysłaną już wielokrotność, to obliczamy kolejną
K08:         Jeśli V[i] < minv, to minvV[i] ; zapamiętujemy najmniejszą z wielokrotności
K09:     sminv; ; zapamiętujemy w s znalezioną najmniejszą z wielokrotności
K10:     Jeśli s > b, to zakończ ; jeśli jest ona poza przedziałem <a,b>, to kończymy
K11:     Pisz s ; inaczej wyprowadzamy s i kontynuujemy pętlę
K12: Idź do K05  

 

Algorytm wygląda na dłuższy niż w pierwszej wersji. Jednakże działa on efektywniej, ponieważ w pętli głównej nie wykonujemy dzieleń, a jedynie dodawania oraz pętla ta nie wykonuje pustych przebiegów – przy każdym obiegu wyprowadzana jest jedna liczba. Korzyści ujawnią się szczególnie przy dużym przedziale <a,b> oraz znacznej różnicy pomiędzy dzielnikami.

 

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 spodziewa się w pierwszym wierszu liczb a i b. W drugim wierszu należy podać n = 1...1000, a następnie w n wierszach kolejne podzielniki (nie muszą być uporządkowane).

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

-100 100
3
5
12
17

Lazarus
// Liczby podzielne - wersja 2
// Data   : 12.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

const MAXZ = 2147483647;
const MAXP = 1000;

var a,b,i,n,s,minv : longint;
    P,V : array[0..MAXP-1] of longint;

begin
  readln(a,b);
  readln(n);
  for i := 0 to n-1 do
  begin
    readln(P[i]);
    if P[i] < 0 then P[i] := -P[i];
    if a < 0 then
      V[i] := (a div P[i]) * P[i]
    else
      V[i] := ((a + P[i] - 1) div P[i]) * P[i];
  end;
  s := a - 1;
  while true do
  begin
    minv := MAXZ;
    for i := 0 to n-1 do
    begin
      if V[i] = s then inc(V[i],P[i]);
      if V[i] < minv then minv := V[i];
    end;
    s := minv;
    if s > b then break;
    write(s,' ');
  end;
  writeln;
end.
Code::Blocks
// Liczby podzielne - wersja 2
// Data   : 12.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

const int MAXZ = 2147483647;
const int MAXP = 1000;

int main()
{
  int a,b,i,n,s,minv;
  int P[MAXP],V[MAXP];

  cin >> a >> b >> n;
  for(i = 0; i < n; i++)
  {
    cin >> P[i];
    if(P[i] < 0) P[i] = -P[i];
    if(a < 0)
      V[i] = (a / P[i]) * P[i];
    else
      V[i] = ((a + P[i] - 1) / P[i]) * P[i];
  }
  s = a - 1;
  while(true)
  {
    minv = MAXZ;
    for(i = 0; i < n; i++)
    {
      if(V[i] == s) V[i] += P[i];
      if(V[i] < minv) minv = V[i];
    }
    s = minv;
    if(s > b) break;
    cout << s << " ";
  }
  cout << endl;
  return 0;
}
Free Basic
' Liczby podzielne - wersja 2
' Data   : 12.03.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Const MAXZ = 2147483647
Const MAXP = 1000

Dim As Integer a,b,i,n,s,minv
Dim As Integer P(MAXP),V(MAXP)

Input a,b
Input n
For i = 0 To n-1
  Input P(i)
  If P(i) < 0 Then P(i) = -P(i)
  If a < 0 Then
    V(i) = (a \ P(i)) * P(i)
  Else
    V(i) = ((a + P(i) - 1) \ P(i)) * P(i)
  End If
Next
s = a - 1
Do
  minv = MAXZ
  For i = 0 To n - 1
    If V(i) = s Then V(i) += P(i)
    If V(i) < minv Then minv = V(i)
  Next
  s = minv
  If s > b Then Exit Do
  Print s;" ";
Loop
Print
End

 

Problem nr 2

W przedziale <a,b> liczb całkowitych wyszukać wszystkie liczby podzielne przez każdą z liczb z zadanego zbioru P liczb względnie pierwszych

 

 

Jeśli liczba ma być podzielna przez każdy z podzielników, to również musi być podzielna przez ich iloczyn. Zatem w podejściu 1 obliczamy iloczyn kolejnych podzielników, a następnie w pętli przebiegającej przez kolejne liczby z przedziału <a,b> sprawdzamy, czy są one podzielne przez ten iloczyn. Jeśli tak, to wyprowadzamy je na wyjście.

W podejściu drugim obliczamy najmniejszą wielokrotność iloczynu podzielników, która wpada w przedział <a,b> (patrz powyżej – rozwiązanie alternatywne). Następnie w pętli dopóki wielokrotność jest mniejsza lub równa b, wyprowadzamy ją na wyjście i obliczamy następną dodając iloczyn podzielników.

W ramach ćwiczeń proponuję czytelnikom samodzielne utworzenie algorytmów oraz na ich podstawie odpowiednich programów.

 

 

Problem nr 3

W przedziale <a,b> liczb całkowitych wyszukać wszystkie liczby niepodzielne przez żadną z liczb z zadanego zbioru P.

 

 

Stosując pierwsze podejście przebiegamy przez kolejne liczby w przedziale <a,b>. Każdą liczbę sprawdzamy na podzielność przez podzielniki z P. Jeśli któryś z nich dzieli liczbę, to przechodzimy do następnej liczby w <a,b>. Jeśli żaden nie dzieli liczby, liczbę wyprowadzamy na wyjście.

 

Algorytm wyszukiwania liczb niepodzielnych przez zadane liczby

Wejście
a     początek przedziału, a Z
b  – koniec przedziału, b Z
n  – liczba podzielników,  n N
P  – tablica, której kolejne elementy są podzielnikami. Elementy Z. Numeracja elementów od zera.
Wyjście:

Kolejne liczby z przedziału <a,b> niepodzielne przez żaden z podzielników w P

Zmienne pomocnicze
i    przebiega przez kolejne liczby w <a,b>. i Z
j    przebiega przez indeksy podzielników w P. j N
Lista kroków:
K01: Dla i = a,a+1,...,b wykonuj kroki K02...K04 ; pętla przebiegająca przez kolejne liczby z <a,b>
K02:     Dla j = 0,1,...,n-1 wykonuj krok K03 ; pętla sprawdzająca podzielność przez dzielniki z P
K03:         Jeśli i mod P[j] = 0, to następny obieg pętli K01 ; jeśli jakiś dzielnik dzieli i, przechodzimy do następnej liczby
K04:     Pisz i ; jeśli żaden dzielnik nie dzieli i, wyprowadzamy je
K05: 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 spodziewa się w pierwszym wierszu liczb a i b. W drugim wierszu należy podać n = 1...1000, a następnie w n wierszach kolejne podzielniki (nie muszą być uporządkowane).

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

-100 100
4
2
3
5
7

 

Lazarus
// Liczby niepodzielne
// Data   : 12.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

program prg;

const MAXP = 1000;

var a,b,i,j,n : longint;
    P : array[0..MAXP-1] of longint;
    t : boolean;

begin
  readln(a,b);
  readln(n);
  for i := 0 to n - 1 do readln(P[i]);
  for i := a to b do
  begin
    t := true;
    for j := 0 to n - 1 do
      if i mod P[j] = 0 then
      begin
        t := false;
        break;
      end;
    if t then write(i,' ');
  end;
  writeln;
end.
Code::Blocks
// Liczby niepodzielne
// Data   : 12.03.2008
// (C)2012 mgr Jerzy Wałaszek
//----------------------------

#include <iostream>

using namespace std;

const int MAXP = 1000;

int main()
{
  int a,b,i,j,n,P[MAXP];
  bool t;

  cin >> a >> b >> n;
  for(i = 0; i < n; i++) cin >> P[i];
  for(i = a; i <= b; i++)
  {
    t = true;
    for(j = 0; j < n; j++)
      if(i % P[j] == 0)
      {
        t = false;
        break;
      }
    if(t) cout << i << " ";
  }
  cout << endl;
  return 0;
}
Free Basic
' Liczby niepodzielne
' Data   : 12.03.2008
' (C)2012 mgr Jerzy Wałaszek
'----------------------------

Const MAXP = 1000

Dim As Integer a,b,i,j,n,P(MAXP),t

Input a,b
Input n
For i = 0 To n - 1: Input P(i): Next
For i = a To b
  t = 1
  For j = 0 To n - 1
    If i Mod P(j) = 0 Then
      t = 0
      Exit For
    End If
  Next
  If t Then Print i ;" ";
Next
Print
End
Wynik
-100 100
4
2
3
5
7
-97 -89 -83 -79 -73 -71 -67 -61 -59 -53 -47 -43 -41 -37 -31 -29 -23 -19 -17 -13
-11 -1 1 11 13 17 19 23 29 31 37 41 43 47 53 59 61 67 71 73 79 83 89 97

Liczby niepodzielne
(C)2012 mgr Jerzy Wałaszek

a = , b = dzielniki =


...

 



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.