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

Elementy pomocnicze:

i : przebiega przez kolejne liczby w przedziale <ab>; i ∈ C.
j
 : przebiega przez numery kolejnych podzielników P; j ∈ N.

Lista kroków:

K01: Dla i = a,a+1,…,b:    ; przechodzimy przez kolejne 
     wykonuj kroki K02…K03 ; liczby z przedziału <a,b>
K02:   Dla j = 0,1,…,n-1:  ; sprawdzamy, czy liczba i dzieli się 
       wykonuj kroki K03…K05 ; przez jeden z podzielników z tablicy P.
K03:   Jeśli i mod P[j]  0, ; nie dzieli się, następny podzielnik
       to następny obieg pętli K02
K04:   Pisz i ; dzieli się, wypisz liczbę i
K05:   Następny obieg pętli K01 ; przerywamy pętlę K02
K06: 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 trzecim wierszu jest n podzielników (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
    read(P[i]);
  readln(); // Koniec wiersza danych
  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
Const MAXP = 1000

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

Open Cons For Input As #1

Input #1,a,b,n

For i = 0 To n-1
  Input #1,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

Close #1

End
Python (dodatek)
# Liczby podzielne
# Data   : 02.02.2024
# (C)2024 mgr Jerzy Wałaszek
#----------------------------

# odczyt i przygotowanie danych

arr = input().split(" ")
a = int(arr[0])
b = int(arr[1])
n = int(input())
p = input().split(" ")
for i in range(n):
    p[i] = int(p[i])

# obliczenia

for i in range(a,b+1):
    for j in range(n):
        if not(i%p[j]):
            print(i,end=" ")
            break
print()

 

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 <ab>. 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 <ab> podzielne przez jeden z podzielników w P.

Elementy 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, ; ujemne podzielniki zamieniamy
       to P[i] ← -P[i] ; na dodatnie
K03:   Jeśli a < 0, to ; wyznaczamy pierwszą wielokrotność 
         V[i] ← (a div P[i])×P[i] ; podzielnika P[i]
       inaczej
         V[i] ← ((a+P[i]-1) div P[i])×P[i]
K04: sa-1 ; s zapamiętuje wysłaną na wyjście liczbę.
     ; Nadajemy jej wartość niemożliwą
K05: minvMAXZ ; 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, ; jeśli trafimy na wysłaną już wielokrotność,
       to V[i] ← V[i]+P[i] ; to obliczamy kolejną
K08:   Jeśli V[i] < minv, ; zapamiętujemy najmniejszą z wielokrotności
       to minvV[i]
K09: sminv ; zapamiętujemy w s znalezioną najmniejszą z wielokrotności
K10: Jeśli s > b, ; jeśli jest ona poza przedziałem <a,b>, to kończymy
     to zakończ
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 <ab> 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
Python (dodatek)
# Liczby podzielne - wersja 2
# Data   : 13.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ----------------------------

Maxz = 2147483647

v = []
p = []
arr = input().split(" ")
a = int(arr[0])
b = int(arr[1])
n = int(input())
for i in range(n):
    p.append(int(input()))
    if p[i] < 0: p[i] = -p[i]
    if a < 0:
        v.append((a // p[i]) * p[i])
        if v[i] < a: v[i] += p[i]  # korekcja !!!
    else:
        v.append(((a + p[i] - 1) // p[i]) * p[i])
s = a - 1
while True:
    minv = Maxz
    for i in range(n):
        if v[i] == s: v[i] += p[i]
        if v[i] < minv: minv = v[i]
    s = minv
    if s > b: break
    print(s, end=" ")
print()

Na początek:  podrozdziału   strony 

Problem nr 2

W przedziale <ab> 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.

podejściu drugim obliczamy najmniejszą wielokrotność iloczynu podzielników, która wpada w przedział <ab> (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 <ab> 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 <ab>. 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 <ab>. 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 ∈ C.
b
 : koniec przedziału; b ∈ C.
n
 : liczba podzielników; n ∈ N.
P : tablica, której kolejne elementy są podzielnikami; P ∈ C. Numeracja elementów od zera.

Wyjście:

Kolejne liczby z przedziału <ab> niepodzielne przez żaden z podzielników w tablicy P.

Elementy pomocnicze:

i : przebiega przez kolejne liczby w <ab>; i ∈ C.
j
 : przebiega przez indeksy podzielników w tablicy P; j ∈ N.

Lista kroków:

K01: Dla i = a,a+1,…,b: ; pętla przebiegająca przez
     wykonuj kroki K02…K04 ; kolejne liczby z <a,b>
K02:   Dla j = 0, 1, …, n - 1: ; pętla sprawdzająca podzielność
       wykonuj krok K03 ; przez dzielniki z P
K03:     Jeśli i mod P[j] = 0, ; jeśli jakiś dzielnik dzieli i, 
         to następny obieg pętli K01 ; 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
Python (dodatek)
# Liczby niepodzielne
# Data   : 03.02.2024
# (C)2024 mgr Jerzy Wałaszek
# ----------------------------

p = []

arr = input().split(" ")
a = int(arr[0])
b = int(arr[1])
n = int(input())

for i in range(n):
    p.append(int(input()))

for i in range(a, b + 1):
    t = True
    for j in range(n):
        if not (i % p[j]):
            t = False
            break
    if t:
        print(i, end=" ")

print()
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
©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.