Гладкое число

 В теории чисел гладким числом называется целое число, всепростые делители которого малы. Поскольку понятие «делители малы» можетбыть истрактовано вольно, чаще всего гладким числом называют такое, чьипростые делители не превосходят 10 (то есть, по сути равны 2,3,5 или 7).
 Гладкие числа особенно важны в алгоритмах факторизации.

Определение


 Натуральное число называется B-гладким, если все его простыеделители не превосходят B.

Пример


 Число 2000 имеет следующее разложение на множители: 24× 53. Поэтому 2000 — это 5-гладкое число, а также6-гладкое число и так далее, но не 4-гладкое.

Распределение


 Пусть Ψ(x,y) обозначает количество y-гладких целых чисел, непревосходящих x.
 Если граница гладкости B фиксирована и мала, верна следующаяоценка для Ψ(x,B):

Ψ(x,B)1π(B)!pBlogxlogp.
 Иным образом, определим u как u = log x / logy: то есть, x = yu. Тогда

Ψ(x,y)=xρ(u)+O(xlogy),
 где ρ(u) — функция Дикмана.