4 не является простым числом. 92.243.118.210 04:48, 10 апреля 2013 (UTC)
Эффективное деление и малая теорема Ферма, то есть деление в много проходов 2^p - 2. править
Есть пригодный алгоритм деления, на примере 123 / 45. Делим 123 на 4, получим частное 30. Делим 30 на 15, получим 2. К разрядам делителя приписывая 1 слева от старшего разряда. Итак посчитав 2^p - 2 где p проверяемое число и учитывая что в записи это последовательность двоичных 1 кроме младшего разряда, делим в много проходов число на разряды делителя p. При этом, желательно, используется только доступная виртуальная память, та которая не записана в своп. Вероятно это также быстро позволяет произвести тест простоты числа.