Почему мы проверяем квадратный корень из простого числа, чтобы определить, является ли оно простым?

Question

Чтобы проверить, является ли число простым или нет, почему мы должны проверять, делится ли оно только до квадратного корня из этого числа?

Answer 1

Если число n не является простым, оно может быть разделено на два фактора a и b:

n = a * b

Если бы a и b были больше квадратного корня из n, тогда a * b было бы больше, чем n. Поэтому хотя бы один из этих факторов должен быть меньше или равен квадратному корню из n, и если мы не можем найти какие-либо факторы, меньшие или равные квадратному корню, n должно быть простым.

Answer 2

Допустим, m = sqrt(n), затем m × m = n. Теперь, если n не простое число, то n можно записать как n = a × b, поэтому m × m = a × b. Обратите внимание, что m является действительным числом, тогда как n, a и b являются натуральными числами.

Теперь может быть 3 случая:

1. a> m ⇒ b
2. a = m ⇒ b = m
3. a m

Во всех 3 случаях min(a, b) ≤ m. Следовательно, если мы будем искать до m, мы обязательно найдем хотя бы один фактор n, которого достаточно, чтобы показать, что n не является простым.

Answer 3

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

Answer 4

Более интуитивное объяснение было бы: -

Квадратный корень из 100 равен 10. Скажем, axb = 100, для различных пар a и b.

Если a == b, то они равны, и квадратный корень из 100, точно.Что равно 10.

Если один из них меньше 10, другой должен быть больше.Например, 5 x 20 == 100. Один больше 10, другой меньше 10.

Думая об аксбе, если один из них падает, другой должен стать больше, чтобы компенсировать, поэтомупродукт остается на уровне 100. Они вращаются вокруг квадратного корня.

Квадратный корень из 101 составляет около 10,049875621.Поэтому, если вы проверяете число 101 на простоту, вам нужно пробовать целые числа до 10, включая 10. Но сами по себе 8, 9 и 10 не являются простыми, поэтому вам нужно проверить только до 7, чтопростое число.

Потому что, если есть пара факторов с одним из чисел больше 10, другой из пары должен быть меньше 10. Если меньший не существует, совпадение большекоэффициент 101.

Если вы тестируете 121, квадратный корень равен 11. Вы должны проверить простые целые числа от 1 до 11 (включительно), чтобы убедиться, что оно идет равномерно.11 идет в 11 раз, поэтому 121 не простое число.Если бы вы остановились на 10 и не проверяли 11, вы бы пропустили 11.

Вы должны проверять каждое простое число, большее 2, но меньше или равное квадратному корню, при условии, что вы проверяете тольконечетные числа.

`

Answer 5

Предположим, n не простое число (больше 1). Так что есть числа a и b такие, что

n = ab      (1 < a <= b < n)

Умножив соотношение a<=b на a и b, мы получим:

a^2 <= ab
 ab <= b^2

Поэтому: (обратите внимание, что n=ab)

a^2 <= n <= b^2

Следовательно: (Обратите внимание, что a и b положительны)

a <= sqrt(n) <= b

Таким образом, если число (больше 1) не является простым, и мы проверяем делимость с точностью до квадратного корня из числа, мы найдем один из факторов.

Answer 6

Предположим, что данное целое число N не простое,

Тогда N можно разложить на два множителя a и b, 2 <= a, b < N, таких что N = a*b.Очевидно, что они оба не могут быть больше, чем sqrt(N) одновременно.

Предположим без ограничения общности, что a меньше.

Теперь, если вы не можете найти делитель N, принадлежащий диапазону [2, sqrt(N)], что это делает?значит?

Это означает, что N не имеет делителя в [2, a] как a <= sqrt(N).

Следовательно, a = 1 и b = n и, следовательно, По определению N является простым .

...

Дальнейшее чтение, если вы не удовлетворены:

Возможно множество различных комбинаций (a, b).Допустим, они:

(a ₁ , b ₁ ), (a ₂ , b ₂ ), (a ₃ , b ₃ ), ....., (a _k , b _k ).Без ограничения общности предположим, что _i i , 1<= i <=k.

Теперь, чтобы показать, что N не является простым, этодостаточно, чтобы показать, что ни один из _i не может быть разложен дальше.И мы также знаем, что _i <= <code>sqrt(N), и, таким образом, вам нужно проверить до sqrt(N), который будет охватывать все _i .И, следовательно, вы сможете сделать вывод, является ли N простым.

...

Answer 7

Это все на самом деле просто базовое использование факторизации и квадратных корней.

Это может показаться абстрактным, но в действительности это просто связано с тем фактом, что максимально возможный факториал не простого числа должен был быбыть его квадратным корнем, потому что:

sqrroot(n) * sqrroot(n) = n.

Учитывая, что, если любое целое число выше 1 и ниже или доsqrroot(n) делится равномерно на n, тогда n не может быть простым числом.

Пример псевдокода:

i = 2;

is_prime = true;

while loop (i <= sqrroot(n))
{
  if (n % i == 0)
  {
    is_prime = false;
    exit while;
  }
  ++i;
}

Answer 8

Итак, чтобы проверить, является ли число N простым или нет. Нам нужно только проверить, делится ли N на числа <= SQROOT (N). Это потому, что если мы разложим N на любые 2 множителя, скажем, X и Y, т.е. N = X <em>Y. Каждое из X и Y не может быть меньше SQROOT (N), потому что тогда X Y N

Следовательно, один фактор должен быть меньше или равен SQROOT (N) (в то время как другой фактор больше или равен SQROOT (N)). Поэтому, чтобы проверить, является ли N простым, нам нужно проверить только эти числа <= SQROOT (N). </p>

Answer 9

Допустим, у нас есть число «a», которое не является простым [не простое / составное число означает - число, которое может быть равномерно разделено на числа, отличные от 1 или самого себя. Например, 6 можно разделить равномерно на 2 или на 3, а также на 1 или 6].

6 = 1 × 6 или 6 = 2 × 3

Так что теперь, если «а» не простое, то его можно разделить на два других числа, и предположим, что эти числа «b» и «c». Что означает

а = Ь * с.

Теперь, если "b" или "c", любой из них больше квадратного корня из "a", чем умножение "b" и "c" будет больше, чем "a".

Итак, «b» и «c» всегда <= квадратный корень из «a», чтобы доказать уравнение «a = b * c». </p>

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

Answer 10

Учитывая любое число n, один из способов найти его множители - получить квадратный корень p:

sqrt(n) = p

Конечно, если мы умножим p на себя, то получим n:

p*p = n

Это может быть переписано как:

a*b = n

Где p = a = b. Если a увеличивается, то b уменьшается для поддержания a*b = n. Следовательно, p является верхним пределом.