Простые числа. Способы проверки

Метод Фиббоначи.

    Этот метод определения простоты чисел, по-видимому, первым опубликовал в 1902 г. Леонардо Пизанский в книге, названной "Книга абака". Абак- это древний вычислительный инструмент, подобный русским счетам. Леонардо родился в итальянском городе Пизе около 1170 г. в семье городского писаря. Отец его имел смешное прозвище Боначчо (добродушный), имя Фиббоначи (сын Боначчо) закрепилось за Леонардо и получило широкую известность

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

Метод пробных делений

    Количество испытываемых делителей можно значительно сократить. Например, если N не делится на 2, то незачем испытывать в роли делителей N четные числа, а если N не делится на 3, то числа, делящиеся на 3. В результате мы исключим из испытываемых делителей  все числа, которые при делении на 6 дают остатки 0, 2, 3, 4, т. е. останутся только числа вида 6k+1 и 6k=5. Получается следующий усовершенствованный метод пробных делений:

• Проверить, делиться ли число N на 2 или 3. Если делится, то N - составное число.
• Иначе составить таблицу пробных делителей. В ней первая строка имеет вид 1, 5, 

  1 5 7 11 13 17 19 23 25 29 31 35

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

    Метод пробных делений позволяет также находить и небольшие делители больших составных чисел.