while (i <= sqrt (static_cast <double>(n))

Question

В книге "С ++ без страха: руководство для начинающих, которая заставляет вас чувствовать себя умнее" в главе (2): Решения, Решения вы можете увидеть этот код кода как часть программы простых чисел:

while (i<=sqrt(static_cast<double>(n))

При условии, что «i» было инициализировано как «2», а «n» - ввод пользователя.

Почему мы сравниваем с «sqrt» из «n», а не с «n»"Сам?

Спасибо.

Answer 1

Поскольку вы не получите никаких коэффициентов для непростых чисел, которые> sqrt (n) (вы бы уже нашли другой, меньший коэффициент).

Хотя это действительно плохой тестгораздо лучше написать это как:

while (i*i <= n)

Answer 2

Потому что если число имеет факторы, отличные от самого себя и 1, то хотя бы один из этих факторов будет меньше, чем число числа.

Answer 3

Алгоритмически правильно проверять возможные факторы вплоть до квадратного корня вашей цели.

Если N - это число, которое может быть или не быть простым, если нет факторов (не считая 1) до sqrt (N), то N должно быть простым. Сам sqrt (N) вполне может быть его единственным основным фактором (например, 9, что 3 * 3).

Если мы собираемся проверить, является ли 17 простым, мы знаем, что sqrt (17) чуть выше 4. 2, 3 и 4 не делятся на 17, поэтому оно должно быть простым, так как 5 больше.

Это должно быть так, потому что 17/5 будет меньше 5 и тоже должно быть фактором, но мы знаем, что нет факторов меньше 5.

Программно, конечно, код не оптимален, так как вы бы не использовали двойные и квадратные корни, а что-то вроде (i * i <= N) </p>

Answer 4

Код выглядит так:

i = 2;
while (i <= sqrt(static_cast<double>(n)) {
  if (n % i == 0) is_prime = false;
  i++;
}

Таким образом, цикл проверяет, делится ли n на i без остатка.Очевидно, нужно только проверить это до (и включая) квадратного корня из n (потому что если n / p = q, то также n / q = p).

Answer 5

while (i<=sqrt(static_cast<double>(n))

Эквивалентно

while(n >= i*i)

Выбор автора первого решения может зависеть от других частей кода.