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

давайте 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 не премьер.

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

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

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

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

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

думая о x b, если один из них идет вниз, другой должен получить больше, чтобы компенсировать, поэтому продукт остается на 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, но меньше или равно квадратному корню, предполагая, что вы тестируете только нечетные числа.

'

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

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

путем умножения отношении a<=b by a и b получаем:

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

предположим, что заданное целое число 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). Без потери общности, предположим, что_яя,1<= i <=k.

теперь, чтобы иметь возможность показать, что N не является простым достаточно показать, что ни один из_я можно далее разложить на множители. И мы также знаем, что A_яsqrt(N) и таким образом вам нужно проверить до sqrt(N), который будет охватывать все_я. И, следовательно, вы сможете сделать вывод, является ли или нет N премьер.

...

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

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

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;
}

Итак, чтобы проверить, является ли число N простым или нет. Нам нужно только проверить, делится ли N на числаY. Каждый из X и Y не может быть меньше SQROOT (N), потому что тогда XY N

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

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

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

Итак, если " a "не является простым, то его можно разделить на два других числа, и предположим, что эти числа являются" b "и"c". Что означает

a=b * c.

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

Итак, "b" & "c" всегда

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

пусть n не является простым. Поэтому он имеет по крайней мере два целочисленных фактора больше 1. Пусть f-наименьший из N таких факторов. Предположим, что Ф > функция sqrt Н. Тогда N/F представляет собой целое число ЛТР функция sqrt н, таким образом, меньше, чем F. Следовательно, F не может быть наименьший коэффициент "Н". Reductio ad absurdum; наименьший коэффициент n должен быть LTE sqrt n.

чтобы проверить простоту числа, n, можно было бы ожидать цикл, такой как следующий в первую очередь:

bool isPrime = true;
for(int i = 2; i < n; i++){
    if(n%i == 0){
        isPrime = false;
        break;
    }
}

что выше цикл делает это : для данного 1 , он проверяет, является ли n/i целым числом (оставляет остаток 0). Если существует i, для которого n/i является целым числом, то мы можем быть уверены, что n не является простым числом, и в этот момент цикл завершается. Если для no i, n / i-целое число, то n-простое число.

как с каждый алгоритм, мы спрашиваем : можем ли мы сделать лучше ?

давайте посмотрим, что происходит в приведенном выше цикле.

последовательность i идет: i = 2, 3, 4,... , n-1

и последовательность целочисленных проверок идет: j = n/i, который является n/2, n/3, n / 4, ... , n / (n-1)

Если для некоторых i = a, n / a является целым числом, то n / a = k (integer)

или n = ak, ясно n > k > 1 (Если k = 1, то a = n, но я никогда не достигну n; и если k = n, то a = 1, но я начинаю форму 2)

кроме того, n/k = a, и, как указано выше, a-это значение i so n > a > 1.

Итак, a и k являются целыми числами между 1 и n (exclusive). Поскольку i достигает каждого целого числа в этом диапазоне, на некоторой итерации i = a и на некоторой другой итерации i = k. Если тест на примитивность n не выполняется для min(a,k), он также не будет выполнен для max(a,k). Поэтому нам нужно проверить только один из этих двух случаев, если min (a, k) = max (a,k) (где две проверки сводятся к одному), т. е. a = k, at какая точка a*a = n, что означает a = sqrt (n).

= sqrt(n) (т. е. max(a,k)), то он также потерпел бы неудачу для некоторого i

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

sqrt(n) = p

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

p*p = n

его можно переписать как:

a*b = n

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