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 podzielne lub niepodzielne przez zadane podzielniki

SPIS TREŚCI
Podrozdziały

Problem nr 1

W przedziale [ a, b  ] liczb całkowitych należy wyszukać wszystkie liczby podzielne przez jedną z liczb z zadanego zbioru P.

Problem nr 1

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  ∈ C.
b  – koniec przedziału, b  ∈ C, a  < b.
n  – liczba podzielników, n  ∈ N.
P  – tablica, której kolejne elementy są podzielnikami. P [ i  ]  ∈ C; i  = 0, 1, ..., n - 1.

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  ∈ C.
j  – przebiega przez numery kolejnych podzielników w P, j  ∈ N.

Lista kroków:

K01: Dla i  = a, a + 1, ..., b :
wykonuj kroki K02...K03
przechodzimy przez kolejne liczby z przedziału <a, b>
K02:     Dla j  = 0, 1, ..., n - 1:
    wykonuj krok K03
sprawdzamy, czy liczba i dzieli się przez jeden z podzielników z tablicy P.
K03:         Jeśli i  mod P [ j ] = 0,
        to pisz i
            i następny obieg pętli K01
Jeśli tak, wyprowadzamy i, przerywamy pętlę K02
K04: 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 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
Pascal
// Liczby podzielne
// Data   : 11.03.2008
// (C)2020 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.
C++
// Liczby podzielne
// Data   : 11.03.2008
// (C)2020 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;
}
Basic
' Liczby podzielne
' Data   : 11.03.2008
' (C)2020 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)2020 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  ∈ C.
b  – koniec przedziału, b  ∈ C.
n  – liczba podzielników, n  ∈ N.
P  – tablica, której kolejne elementy są podzielnikami. P [ i  ]  ∈ C; i  = 0, 1, ..., n - 1. 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  ∈ C.
s  – liczba przesłana na wyjście, s  ∈ C.
minv  – minimalna wartość wielokrotności podzielników z P. minv  ∈ C.
V  – tablica wielokrotności podzielników. Elementy  ∈ C. 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: s  ← a  - 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 minv  ← V [ i ]
zapamiętujemy najmniejszą z wielokrotności
K09:     s  ← minv 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 kroku 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.


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 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
Pascal
// Liczby podzielne - wersja 2
// Data   : 12.03.2008
// (C)2020 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.
C++
// Liczby podzielne - wersja 2
// Data   : 12.03.2008
// (C)2020 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;
}
Basic
' Liczby podzielne - wersja 2
' Data   : 12.03.2008
' (C)2020 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
Na początek:  podrozdziału   strony 

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.

Problem nr 2

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.

Na początek:  podrozdziału   strony 

Problem nr 3

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

Problem nr 3

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, aC.
b  – koniec przedziału, bC.
n  – liczba podzielników, nN.
P  – tablica, której kolejne elementy są podzielnikami. P  ∈ C. Numeracja elementów od zera.

Wyjście:

Kolejne liczby z przedziału [ a, b  ] niepodzielne przez żaden z podzielników w tablicy P.

Zmienne pomocnicze:

i  –  przebiega przez kolejne liczby w [ a, b  ]. iC.
j    przebiega przez indeksy podzielników w tablicy 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  

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 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
Pascal
// Liczby niepodzielne
// Data   : 12.03.2008
// (C)2020 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.
C++
// Liczby niepodzielne
// Data   : 12.03.2008
// (C)2020 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;
}
Basic
' Liczby niepodzielne
' Data   : 12.03.2008
' (C)2020 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)2020 mgr Jerzy Wałaszek
a =
b =
dzielniki =

...

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.