×
Jak to funguje?
🧬 Prime DNA
Prvočísla zakódujeme pomocí mezer (gaps) mezi nimi.
Všechny mezery (kromě 2→3) jsou sudé, takže ukládáme gap/2.
Výsledek: ~1 byte na prvočíslo. Pro 78k prvočísel do milionu stačí ~100 KB.
🔬 Factor DNA
Pro faktorizaci předpočítáme SPF (Smallest Prime Factor).
Rozklad pak probíhá opakovaným dělením v O(log n):
60 → SPF=2 → 30 → SPF=2 → 15 → SPF=3 → 5
To je ~50× rychlejší než trial division pro velká čísla.
⚙️ Optimalizace
Wheel mod 30: Přeskočíme násobky 2, 3, 5 (ukládáme jen 27% čísel).
VLC: Malé SPF jsou častější → variabilní kódování šetří bity.