Faktorizace
Faktorizace je proces převedení čísla na součin jeho faktorů, čili rozklad na prvočísla. Rozklad je dle základní věty aritmetiky jednoznačný. Předpokládá se, že faktorizace není jednoduchý problém, na čemž je založena bezpečnost některých šifrovacích algoritmů (například RSA). Prvočíselný rozklad má také využití při výpočtu největšího společného dělitele a nejmenšího společného násobku. Obě tyto hodnoty lze ovšem lépe vypočíst pomocí Euklidova algoritmu.
Příklady
Složitost faktorizace
Častou nejasností ohledně faktorizace je její složitost. Pokud se podíváme na klasický algoritmus, který postupně zkouší dělit číslo až do odmocniny, tak by se zdálo, že je složitost polynomiální (odmocnina). Toto ovšem není pravda, protože se složitost počítá na základě velikosti dat, což není velikost čísla v desítkové soustavě, ale počet míst nutných k zakódování čísla v binární soustavě. Skutečná složitost algoritmu je proto exponenciální.
Kód
/**
* Rozloží číslo n >= 2 na prvočíselné součinitele.
* Součinitele vypíše na obrazovku (do konzole).
*
* @param n číslo, které chceme faktorizovat, n >= 2
*/
public static void faktorizuj(int n) {
int zbytek = n;
for (int i = 2; i <= Math.sqrt(zbytek); i++) {
// Pokud jsme vyzkoušeli všechna čísla menší než odmocnina ze zbytku
// a žádné z nich nedělilo zbytek, je zbytek prvočíslo a můžeme
// ho rovnou vypsat.
// Jinak zkoušíme dělit dalším potenciálním prvočinitelem, dokud
// se to daří.
while (zbytek % i == 0) {
zbytek = zbytek / i;
System.out.print(i + " ");
}
}
// Pokud je zbytek větší než 1, pak je to prvočíslo,
// které je třeba vypsat také.
if (zbytek > 1) {
System.out.print(zbytek);
}
}
/**
* Rozlozi cislo n >= 2 na prvociselne soucinitele.
* Soucinitele vypise na obrazovku (do konzole).
*
* @param n císlo, ktere chceme faktorizovat, n >= 2
*/
void faktorizuj(int n) {
int zbytek = n;
for (int i = 2; i <= sqrt(zbytek); i++) {
// Pokud jsme vyzkouseli vsechna cisla mensi nez odmocnina ze zbytku
// a zadne z nich nedelilo zbytek, je zbytek prvocislo a muzeme
// ho rovnou vypsat.
// Jinak zkousime delit dalsim potencialním prvoèinitelem, dokud
// se to dari.
while (zbytek % i == 0) {
zbytek = zbytek / i;
cout << i << " ";
}
}
// Pokud je zbytek vetsi nez 1, pak je to prvocislo,
// ktere je treba vypsat take.
if (zbytek > 1) {
cout << zbytek;
}
}
/**
* Rozlozi cislo n >= 2 na prvociselne soucinitele.
* Soucinitele vypise na obrazovku (do konzole).
*
* @param $n cislo, ktere chceme faktorizovat, n >= 2
*/
function faktorizuj($n) {
$zbytek = $n;
for ($i = 2; $i <= sqrt($zbytek); $i++) {
// Pokud jsme vyzkouseli vsechna cisla mensi nez odmocnina ze zbytku
// a zadne z nich nedelilo zbytek, je zbytek prvocislo a muzeme
// ho rovnou vypsat.
// Jinak zkousime delit dalsim potencialním prvoèinitelem, dokud
// se to dari.
while ($zbytek % $i == 0) {
$zbytek = $zbytek / $i;
echo $i . " ";
}
}
// Pokud je zbytek vetsi nez 1, pak je to prvocislo,
// ktere je treba vypsat take.
if ($zbytek > 1) {
echo $zbytek;
}
}
