Liczba gładka
Z Wikipedii
W teorii liczb, liczba naturalna m jest nazywana B-gładką, jeśli wszystkie jej dzielniki pierwsze są nie większe niż B.
Przykładowo 103195607040000=2233954 jest 5-gładka, ponieważ jej największym dzielnikiem pierwszym jest 5.
Liczby gładkie przydatne są w niektórych algorytmach teorioliczbowych. Przykładowo niektóre algorytmy FFT, rozkładają problem rozmiaru n na problemy o wielkości jego czynników. Jeśli zaczyna się od liczb gładkich, otrzymuje się małe, szybko rozwiązywalne problemy. Innym przykładem jest Redukcja Pohliga-Hellmana obliczająca logarytm dyskretny. W ogólnym przypadku jest ona algorytmem wykładniczym, ale dla B-gładkich liczb działa w czasie O(B1/2).
Liczbę B-gładkich liczb mniejszych od zadanego x można oszacować przez:
.
