Использование функции sqrt внутри цикла while, не понимаю этого
В настоящее время я прохожу «С++ без страха, третье издание». Меня немного смущает этот блок кода, я понимаю, как оператор if используется, чтобы узнать, делится ли n на i. Я просто не понимаю, в чем смысл цикла while.
Конечно, вы могли бы просто написать код без него, и если цикл if вернется с остатком, то это будет простое число, в противном случае это не будет простое число.
#include <iostream>
#include <cmath>
using namespace std;
int main(){
int n = 0; // Number to test for prime-ness
int i = 2; // Loop counter
bool is_prime = true; // Boolean flag...
// Assume true for now
// Get a number from the keyboard
cout << "Enter a number and press ENTER: ";
cin >> n;
// Test for prime by checking for divisibility
// by all whole numbers from 2 to sqrt(n).
while (i <= sqrt(n)){
if (n % i == 0) { // If i divides n,
is_prime = false; // n is not prime
break; // BREAK OUT OF LOOP NOW!
}
++i; // Add 1 to i.
}
// Print results
if (is_prime) {
cout << "Number is prime." << endl;
} else {
cout << "Number is not prime." << endl;
}
return 0;
}
Я этого не понимаю, пожалуйста, помогите мне.
Подумайте о математике. Факторы идут парами. Если вы всегда смотрите на меньший фактор пары, каким он может быть самым большим? Если вы не найдете коэффициент до этого предела, какой вы можете сделать вывод?
Вы можете написать код без квадратного корня, и он все равно будет работать, но в некоторых случаях будет намного медленнее. Попытайтесь выяснить, почему.
Вам нужно разделить n на 2, 3, 4, 5,..... Цикл while — это итерационный процесс, который позволяет вам сделать именно это. Без него вы просто будете делить n на 2 и всё. Но то, что число не делится на 2, не означает, что оно простое. Если вы говорите о sqrt, обратите внимание, что, например, число 12 будет иметь множители 2x6, 3x4. Если я проверил 2, нет необходимости проверять 6. Если я проверил 3, нет необходимости проверять 4. Таким образом, чтобы сэкономить время, мы проверяем до sqrt n.
Если вам не нравится sqrt или вы не хотите его использовать, замените условие цикла на while (i*i < n)
^ Часто также повышается производительность. i*i намного дешевле, чем извлечение квадратного корня из n
Кстати: n никогда не меняется, поэтому sqrt(n) никогда не меняется, поэтому вызывать его на каждой итерации цикла избыточно и неэффективно. Вам следует вызвать sqrt(n) один раз и сохранить результат в переменной, а затем вместо этого использовать эту переменную в цикле, например: int s = sqrt(n); while (i <= s){ ... }.
Обычно нецелесообразно использовать функцию с плавающей запятой (например, sqrt()) при выполнении вычислений, которые работают с целыми значениями и дают целочисленный результат. Плавающая точка вносит неточность, которая может привести либо к неточным результатам, либо к тому, что циклы будут вести себя не так, как предполагалось (например, повторяя больше или меньше раз, что можно было бы ожидать математически). Быстрый поиск в Google выдаст «целочисленный квадратный корень» (функция, которая выдает наибольшее целочисленное значение, не превышающее математического квадратного корня, вообще без использования плавающей запятой)
Ответы 1
Это крайне важно для эффективной проверки.
Цикл while перебирает потенциальные делители n, начиная с 2 до sqrt(n). Это эффективный способ проверки простоты, потому что:
Вместо проверки всех чисел от
2доn-1проверка доsqrt(n)уменьшает количество итераций; если числоnимеет делитель большеsqr(n), соответствующий соделитель должен быть меньшеsqr(n).Проверяя все возможные делители до
sqrt(n), вы гарантируете, что еслиnявляется составным, вы найдете делитель в этом диапазоне, а если делители не найдены, тоnявляется простым.
Если вы удалите цикл while и просто используете оператор if, вам придется явно перечислить все потенциальные делители, что непрактично и неэффективно. Цикл while обеспечивает систематический способ проверки всех необходимых делителей до sqrt(n).
Я только что понял, что веду себя глупо… большое спасибо
Вы понимаете en.wikipedia.org/wiki/Trial_division?