Количество, сумма, произведение делителей

Отметим, что если не является квадратом натурального числа, то хотя бы одно из чисел не является простым. Докажем это утверждение от противного – тогда простое. Число так как не квадрат, а Следовательно, , при этом поэтому не является простым – противоречие.

Вычеркнем из последовательности все элементы, индексы которых являются квадратами, а все остальные элементы разобьем на пары. Между любыми двумя квадратами находится четное количество чисел (), поэтому такой способ ставит в пару подряд идущие числа. По доказанному, в каждой паре находится не более одного простого элемента, значит среди невычеркнутых элементов есть не более, чем простых. Вычеркнутые элементы могут быть простыми. Их количество равно поэтому общее число простых элементов можно оценить как что и требовалось доказать.