Грубое число (IjrQky cnvlk)

Перейти к навигации Перейти к поиску

Грубое число — положительное целое числом, все простые множители которого больше или равны заданного , например, при говорят о 5-грубых числах. (Иногда по определению требуется, чтобы все простые множители строго превышали .) Понятие возникло в противоположность гладким числам (все делители которых не превосходят заданное ).

Например, каждое нечётное положительное целое число является 3-грубым; каждое положительное целое сравнимое с 1 или 5 по модулю 6, является 5-грубым; каждое положительное целое число является 2-грубым (поскольку все его простые множители, будучи простыми числами, превосходят 1).

Количество грубых чисел может быть асимптотически оценено с использованием функции Бухштаба[англ.][1].

Применяются в задачах криптографии.

Примечания

[править | править код]
  • 2-грубые числа: последовательность A000027 в OEIS
  • 3-грубые числа: последовательность A005408 в OEIS
  • 5-грубые числа: последовательность A007310 в OEIS
  • 7-грубые числа: последовательность A007775 в OEIS
  • 11-грубые числа: последовательность A008364 в OEIS
  • 13-грубые числа: последовательность A008365 в OEIS
  • 17-грубые числа: последовательность A008366 в OEIS
  • 19-грубые числа: последовательность A166061 в OEIS
  • 23-грубые числа: последовательность A166063 в OEIS