Цитата:
|
Сообщение от Одиссей
Не, с калькулятором это совсем не по-пацански.
Чтобы определить непростоту знаю два основных способа:
- предъявить два натуральных делителя
- через малую теорему Ферма (неконструктивно, без делителей).
|
Ага, школьник знает "малую теорему Ферма". Я и то не помню, слышал о ней или нет
Как реально предъявить делители числу, которое еле помещается в одну строку. Мой калькулятор не хочет его представить в нормальном виде, только в экспоненциальной форме, обрезая кучу знаков Это не вариант.
Однако, мы знаем, что наше число оканчивается на единицу (1), более того на ...01. Может быть кто-то подскажет, как дальше.
простые правила, позволяющих найти малые делители числа в десятичной системе счисления:
Число делится на
2 тогда и только тогда, когда последняя цифра делится на 2 (т.е. чётная).
Число делится на
3 тогда и только тогда, когда сумма цифр делится на 3 (т. к. все числа вида 10^n при делении на 3 дают в остатке единицу.).
Число делится на
4 тогда и только тогда, когда число из двух последних цифр делится на 4.
Число делится на
5 тогда и только тогда, когда последняя цифра делится на 5 (т.е. равна 0 или 5).
Число делится на
6 тогда и только тогда, когда оно делится на 2 и на 3 (т.е. оно чётное и сумма его цифр делится на три).
Число делится на
7 тогда и только тогда, когда результат вычитания удвоенной последней цифры из этого числа без последней цифры делится на 7 (т. н. 364 делится на 7 т. к. 36-2*4 = 28 делится на 7).
Число делится на
8 тогда и только тогда, когда число из трех последних цифр делится на 8.
Число делится на
9 тогда и только тогда, когда сумма цифр делится на 9.
Число делится на
10 тогда и только тогда, когда последняя цифра — ноль.
Число делится на
11 тогда и только тогда, когда сумма цифр с чередующимися знаками делится на 11 (т. е. 182919 делится на 11 т. к. 1-8+2-9+1-9 = −22 делится на 11 (т. к. все числа вида 10^n при делении на 11 дают в остатке 1 или -1.).
Число делится на
12 тогда и только тогда, когда оно делится на 3 и на 4.
Число делится на
13 тогда и только тогда, когда результат вычитания последней цифры умноженной на 9 из этого числа без последней цифры делится на 13 (т. н. 858 делится на 13 т. к. 85-9*8 = 13 делится на 13).
Число делится на
14 тогда и только тогда, когда оно делится на 2 и на 7.
Число делится на
15 тогда и только тогда, когда оно делится на 3 и на 5.
Число делится на
25 тогда и только тогда, когда две последние цифры делятся на 25 (без остатка).
Число делится на
1001 тогда и только тогда, когда оно делится на 7, 11 и 13. Если любое трёхзначное число умножить на 1001, то оно повторится ещё 1 раз. Например: 101*1001=101101.
понравилась статья про простые числа
http://www.ega-math.narod.ru/Liv/Zagier.htm