owned this note
owned this note
Published
Linked with GitHub
# Zajęcia trzecie - Operacje na liczbach (30 X)
## Dodatkowe materiały:
- Kody źródłowe które pojawiły się na zajęciach - [link](https://files.wpmii.pl/2021-10-30-kod.zip)
- Zadania do przećwiczenia tematu - [link](https://files.wpmii.pl/2021-10-30-zadania.pdf)
## NWD (największy wspólny dzielnik) i NWW (najmniejsza wspólna wielokrotność)
### Największy wspólny dzielnik:
Standardowym algorytmem do wyznaczania NWD jest "algorytm Euklidesa", który można przedstawić w następujący sposób:
$$
NWD(a,b)_{a\ge b} =
\begin{cases}
a &\text{: $b=0$}\\
NWD(b, a \text{ mod } b) &\text{: wpp.}
\end{cases}
$$
#### Przykładowy przebieg algorytmu dla $a=36$ oraz $b=26$:
$$
\begin{split}
NWD(36,26) &= NWD(26, 10)\\
&= NWD(10, 6) \\
&= NWD(6, 4) \\
&= NWD(4, 2) \\
&= NWD(2, 0) \\
&= 2
\end{split}
$$
#### Implementacje w kodzie:
##### W języku C++:
```c++=
// Podejście rekurencyjne:
int gcdRecursive(int a, int b)
{
if (a < b) // Zamieniamy zmienne a i b
std::swap(a, b); // tak aby warunek a>=b zawsze został
// zachowany
if ( b == 0) // Jeśli wartość zmiennej b wynosi 0,
return a; // zwracamy wartość zmiennej a jako wynik
return gcdRecursive(b, a % b); // wpp. zwracamy NWD(b, a%b) jako wynik.
}
// Podejście iteracyjne:
int gcdIterative(int a, int b)
{
if (a < b) // Zamieniamy zmienne a i b
std::swap(a, b); // tak aby warunek a>=b zawsze został
// zachowany
do
{
a -= b;
if (a < b) // Tak długo jak wartość mniejszej z
std::swap(a, b); // liczb nie wyniesie 0, odejmujemy
// od większej z nich wartość mniejszej.
}
while( b != 0);
return a;
}
```
:::success
Do obliczenia NWD możemy również wykorzystać funkcję z biblioteki ```algorithm```, której przykładowe wywołanie to: ```std::__gcd(a, b)```.
:::
##### W języku python:
```python=
# Podejście rekurencyjne:
def gcdRecursive(a, b):
if a < b:
a, b = b, a # Zamiana wartości zmiennych a i b
if b == 0:
return a
return gcdRecursive(b , a % b)
# Podejście iteracyjne:
def gcdIterative(a, b):
if a < b:
a, b = b, a
while b != 0:
a -= b
if a < b:
a, b = b, a
return a
```
:::success
Do obliczenia NWD możemy również wykorzystać funkcję z modułu ```math```, której przykładowe wywołanie to: ```math.gcd(a, b)```.
:::
### Najmniejsza wspólna wielokrotność:
Do wyznaczenia NWW możemy skorzystać z prostej zależności:
$$
NWW(a,b) = \frac{a \cdot b}{NWD(a,b)}
$$
::: spoiler Dlaczego możemy tak zrobić?
Wiemy, że $NWW(a, b)$ musi być liczbą podzielną zarówno przez $a$ jak i przez $b$. Zatem w rozkładzie na czynniki pierwsze, $NWW(a, b)$ musi składać się z takich samych czynników jak $a$, oraz $b$.
Przemnażając $a$ przez $b$, otrzymujemy właśnie taką liczbę, z tym, że nie koniecznie musi ona być najmniejszą taką liczbą. Dzieląc $a \cdot b$, przez ich największy dzielnik, pozbywamy się z naszego potencjalnego $NWW$, duplikacji wspólnych czynników pierwszych dla $a$ i $b$, i w skutek tego, rzeczywiście otrzymujemy ich najmniejszą wspólną wielokrotność.
Przykład:
$$
\begin{split}
a &= 20 = 2 \cdot 2 \cdot 5 \\
b &= 42 = 2 \cdot 3 \cdot 7 \\
a \cdot b &= 20 \cdot 42 = 840 = 2 \cdot 2 \cdot 2 \cdot 3 \cdot 5 \cdot 7\\
NWD(a,b) &= 2 \\
\\
NWW(a,b) &= \frac{840}{2} = \frac{2 \cdot 2 \cdot 2 \cdot 3 \cdot 5 \cdot 7}{2}\\
NWW(a,b) &= 420 = 2 \cdot 2 \cdot 3 \cdot 5 \cdot 7
\end{split}
$$
:::
## Sprawdzanie pierwszości liczby
Najbardziej standardową metodą na sprawdzenie pierwszości liczby, to sprawdzenie czy nie jest ona podzielna przez liczbę inną niż jeden i siebie samą. Pierwszym, najbardziej intuicyjnym podejściem jest sprawdzanie podzielnośći liczby $n$, przez wszystkie liczby naturalne z przedziału $[2,n)$.
Jednakże bardziej optymalnym rozwiązaniem takiego problemu jest sprawdzanie podzielności tylko w przedziale $[2,\sqrt{n}]$. Takie sprawdzenie pierwszości liczby jest wystarczające z racji na zależność którą spełniają jej dzielniki.
Weźmy przykładowo liczbę 48, jej dzielniki i pierwiastek:
$$
48\mid 1, 2, 4, 6, \sqrt{48} \approx 6.93, 8, 12, 24, 48
$$
Możemy zauważyć, że liczba dzielników mniejszych od $\sqrt{48}$ jest dokładnie taka sama, jak liczba dzielników większych od tej liczby. Ponadto możemy zwrócić uwagę na to, że:
$$
\begin{split}
48 &= 1 \cdot 48 \\
&= 2 \cdot 24 \\
&= 4 \cdot 12 \\
&= 6 \cdot 8 \\
\end{split}
$$
Zatem, wszystkie dzielniki liczby 48, przemnożone parami przez siebie, dadzą nam 48.
**W ogólności:** jeśli $n$ jest podzielne przez $i$, to $n$ musi też być podzielne przez $\frac{n}{i}$.
A więc, jeśli $n$ nie jest podzielne przez żadną z liczb naturalnych z przedziału $[2,\sqrt{n}]$, to nie będzie też podzielne przez żadną inną liczbę większą niż $\sqrt{n}$.
#### Implementacje w kodzie:
##### W języku C++:
```c++=
bool isPrime(int n)
{
if ( n <= 1) // Jeżeli n jest mniejsze
return false; // bądź równe 1, to z definicji
// nie może być liczbą pierwszą
// Używając porównania i*i <= n,
// zamiast i <= sqrt(n), unikamy
// ewentualnych problemów z
// porównywaniem liczb
for (int i = 2; i * i <= n; i++) // zmiennoprzecinkowych z całkowitymi
{
if ( n % i == 0) // Jeżeli reszta z dzielenia
return false; // całkowitego n przez dowolną
// z liczb naturalnych z przedziału
// [2, sqrt(n)] wynosi 0,
// to n nie może być l. pierwszą
}
return true;
}
```
##### W języku python:
```python=
def isPrime(n):
if n <= 1:
return False
i = 2
while i * i <= n:
if n % i == 0:
return False
i = i + 1
return True
```
## Sito Eratostenesa
Sito Eratostenesa to jedna z najszybszych metod wyznaczania wszystkich liczb pierwszych z przedziału $[2,n]$.
Zasada jego działania jest następująca:
W pierwszym kroku algorytmu inicjalizujemy tablicę $T[N]$, wypełnioną 0. Po wykonaniu sita, będziemy uznawać za liczby pierwsze, te liczby $k$, dla których wartość $T[k]$ będzie wynosić $0$.
Na przykład dla $n=15$:
| Indeks (i): | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| -------- | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| Wartość (T[i]): | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Następnie "manualnie" oznaczamy $0$ oraz $1$ jako liczby nie-pierwsze, poprzez ustawienie wartośći $T[0]=T[1]=1$:
| Indeks (i): | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| -------- | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| Wartość (T[i]): | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
Możemy teraz przejść już do właściwej zasady działania sita Eratostenesa. W kolejnych krokach bierzemy najmniejszą aktualnie liczbę pierwszą w tablicy $T$, i oznaczamy wszystkie jej wielokrotności w tablicy $T$ (poza nią samą !), jako liczby nie-pierwsze.
Najpierw oznaczamy w ten sposób wszystkie liczby będące wielokrotnościami dwójki ():
| Indeks (i): | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| -------- | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| Wartość (T[i]): | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
Jak widzimy, w ten sposób już udało nam się "odsiać" z tablicy $T$ wiele z liczb które nie są liczbami pierwszymi (stąd nazwa algorytmu). Jednakże w tablicy $T$ nadal pozostało kilka niepoprawnie oznaczonych liczb, takich jak np. $9$ czy $15$, które nie są liczbami pierwszymi, a mimo to wartośći $T[9]$ i $T[15]$ wynoszą $0$. W kolejnych krokach uda nam się również takie wartości odsiać.
Oznaczmy teraz wszystkie liczby będące wielokrotnościami trójki, jako liczby nie-pierwsze:
| Indeks (i): | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 |
| -------- | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - | - |
| Wartość (T[i]): | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |
Jak możemy zauważyć, w tym momencie już tablica $T$, ma ustawione wartości $0$, tylko na indeksach odpowiadających rzeczywiście liczbom pierwszym.
Właśnie w taki sposób, dla dowolnego $n$, poprzez powielanie kroku usuwania z tablicy $T$, wszystkich wielokrotności aktualnie najmniejszej liczby pierwszej, jesteśmy w stanie wyznaczyć zbiór liczb pierwszych z przedziału $[2,n]$.
#### Implementacje w kodzie:
##### W języku C++:
```c++=
#include <iostream>
//Arbitralnie dobrane N
#define N 1000
void eratostenes(int array[], int n)
{
for(int i=2;i<n;i++)
{
if (array[i] == 0) // Jeżeli i jest oznaczone w tablicy,
{ // jako l. pierwsza, to oznaczamy
for(int j=i*2;j<n;j+=i) // jej wszystkie wielokrotnośći
{ // jako l. złożone.
array[j]=1;
}
}
}
}
int main()
{
int primes[N] = { 1, 1, 0 }; // Inicjalizacja tablicy z
// wartościami 1 na pierwszych
// dwóch indeksach, i z zerami
// na pozostałych
eratostenes(primes,N); // Wywołanie sita na
// przygotowanej przez nas tablicy
for(int i=0;i<N;i++)
{
if(primes[i] == 0)
std::cout << i << std::endl;
}
return 0;
}
```
##### W języku python:
```python=
N = 1000
def eratostenes(numbersArray, n):
for i in range(2, n):
for j in range(i*2, n, i):
numbersArray[j] = 1
numbersArray = [0] * N # Inicjalizacja tablicy
# wypełnionej N zerami
numbersArray[0] = 1
numbersArray[1] = 1
eratostenes(numbersArray, N)
for i in range(0, N):
if numbersArray[i] == 0:
print(i)
```
## Sprawdzanie doskonałości liczb
Liczby doskonałe, to liczby naturalne które są równe sumie swoich dzielników właściwych, tj. mniejszych od niej.
Do wyznaczenia dzielników liczby, możemy wykorzystać metodę zbliżoną do sprawdzania pierwszośći liczby, tj. sprawdzać dzielniki tylko do pierwiastka z liczby, i wykorzystać fakt, że jeśli pewna liczba $k$ jest dzielnikiem liczby $n$, to również $\frac{n}{k}$ będzie dzielnikiem liczby $n$.
Jedyne na co w takim wypadku musimy dodatkowo zwracać uwagę, to tzw. liczby kwadratowe, czyli takie których pierwiastek jest liczbą całkowitą. W takim wypadku dodając do sumy dzielników $sqrt(n)$ oraz $\frac{n}{sqrt(n)}$, dodalibyśmy ten sam dzielnik dwa razy.
#### Implementacje w kodzie:
##### W języku C++:
```c++=
// Podstawowa wersja, ze sprawdzaniem kolejno dzielników do n/2.
bool isPerfect(int number)
{
int sumOfDivisors = 0;
for ( int i = 1; i <= number/2; i++)
{
if(number % i == 0)
sumOfDivisors += i;
}
if (number == sumOfDivisors)
return true;
return false;
}
// Zoptymalizowana wersja ze sprawdzaniem dzielników do pierwiastka.
bool isPerfectFaster(int number)
{
int sumOfDivisors = 1;
if (number == 1) return false;
for ( int i = 2; i*i <= number; i++)
{
if(number % i == 0)
{
sumOfDivisors += i;
if(i*i != number) // Sprawdzenie czy nie dodamy
{ // dzielnika drugi raz do sumy
sumOfDivisors += number/i;
}
}
}
if (number == sumOfDivisors)
return true;
return false;
}
```
##### W języku python:
```python=
# Podstawowa wersja, ze sprawdzaniem kolejno dzielników do n/2.
def isPerfect(number):
sumOfDivisors = 0
for i in range (1, number//2+1): # Dzielenie całkowite
# w pythonie obsługuje
# operator "//"
if number % i == 0:
sumOfDivisors = sumOfDivisors + i
if number == sumOfDivisors:
return True
return False
# Zoptymalizowana wersja ze sprawdzaniem dzielników do pierwiastka.
def isPerfectFaster(number):
if number == 1:
return False
sumOfDivisors = 1
i = 2
while i * i <= number:
if number % i == 0:
sumOfDivisors = sumOfDivisors + i
if i * i != number:
sumOfDivisors = sumOfDivisors + number // i
i = i + 1
if number == sumOfDivisors:
return True
return False
```
## Rozkład liczb na czynniki pierwsze
#### Implementacje w kodzie:
##### W języku C++:
```c++=
std::vector<int> findPrimeFactors(int number)
{
std::vector<int> primeFactors;
if ( number == 2 ){
primeFactors.push_back(2);
return primeFactors;
}
int i = 2;
while(number != 1)
{
while( number % i == 0)
{
primeFactors.push_back(i);
number/=i;
}
i++;
}
return primeFactors;
}
```
###### W języku python:
```python=
def findPrimeFactors(number):
primeFactors = []
if number == 2:
primeFactors.append(2)
return primeFactors
i = 2
while number != 1:
while number % i == 0:
primeFactors.append(i)
number = number/i
i = i + 1
return primeFactors
```
