Другие языки программирования и технологии

Есть код который находит простые числа. Почему мы проверяем "d*d <= n" ?

Function isprime(n){
if(n==1) // 1 - не простое число
return false;
// перебираем возможные делители от 2 до sqrt(n)
for(d=2; d*d<=n; d++){
// если разделилось нацело, то составное
if(n%d==0)
return false;
}
// если нет нетривиальных делителей, то простое
return true;
}
ДЗ
Денис Запорожец
398
Попробую формулами показать что проверка больше чем до квадратного корня из числа не нужна.
Если знаете курс школьной математики то из формулы А * В = С число В находится по формуле В = С / А а число А находится по формуле А = С / В. Теперь поразмышляем логически. Почему именно до квадратного корня. Да потому что это своеобразная середина между числами А и В. Если А = квадратному корню числа С то В = А так как А * В = С. А что дальше то меняется? А меняется вот что: если А начинает превышать квадратный корень, то В логично будет меньше чем квадратный корень. А числа которые меньше квадратного корня мы уже проверили что они не делятся нацело. Какова вероятность что при делении на целое число которое больше квадратного корня мы получим целое число меньше квадратного корня, которое уже было проверено и нет целочисленных делителей. Вероятность равна нулю. Надеюсь доступно объяснил. Для закрепления все формулы напишите на листочке и лишний раз подставляйте их в мои рассуждения для понимания о чем я...
Виталий Денисов
Виталий Денисов
15 408
Лучший ответ
Виталий Денисов А и забыл добавить что от перестановки множителей произведение не меняется. То есть А*В = В*А
Для того, чтобы не делать лишних действий. Если ты проверяешь 10000, то понадобится не больше 100 итераций. Выражение d * d <= n аналогично выражению d <= sqrt(n).

Если число составное, то оно обязательно имеет делитель, значение которого не больше квадратного корня этого числа.
Avt. Leonid
Avt. Leonid
59 354
Потому что ты ищешь наименьший из двух (или больше) множителей.
Эдик =*
Эдик =*
95 935

Похожие вопросы