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

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. а> м ⇒ б <м
2. a = m ⇒ b = m
3. <м ⇒ б> м

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

Answer 3

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

Answer 4

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

Квадратный корень из 100 равен 10. Скажем, a x b = 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

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

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

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 7

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

Теперь, чтобы иметь возможность показать, чтоN не является простым, достаточно показать, что ни одно из_{i не} может быть разложено дальше. И мы также знаем, что_я <= sqrt(N)и, следовательно, вам нужно проверить доsqrt(N)который покроет все И, следовательно, вы сможете сделать вывод, действительно ли N прост.

...

Answer 8

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

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

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

а = Ь * с.

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

Таким образом, "b" и "c" всегда <= квадратный корень из "a", чтобы доказать уравнение "a=b*c".

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

Answer 9

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

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

Answer 10

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

sqrt(n) = p

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

p*p = n

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

a*b = n

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

Answer 11

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

Answer 12

Да, как было правильно объяснено выше, достаточно выполнить итерацию до Math.floor квадратного корня числа, чтобы проверить его простоту (поскольку охватывает все возможные случаи деления; и Math.floor, потому что любое целое число выше sqrt уже будет за пределами его диапазона).

Вот фрагмент исполняемого кода JavaScript, который представляет реализацию этого подхода: его "удобство выполнения" достаточно хорошо для проверки простоты чисел до нескольких десятков миллиардов (с помощью функции ниже, проверка, например, числа 10 млрд + займет на большинство 50k+ итераций):

Answer 13

Любое составное число является произведением простых чисел.

Пусть скажут n = p1 * p2, где p2 > p1 и они простые числа.

Если n % p1 === 0 тогда n - составное число.

Если n % p2 === 0 тогда угадай что n % p1 === 0 также!

Так что нет никакого способа, что если n % p2 === 0 но n % p1 !== 0 в то же время. Другими словами, если составное число n может быть разделено равномерно наp2, p3... pi (его больший коэффициент), оно также должно быть разделено на его самый низкий коэффициент p1. Оказывается, самый низкий фактор p1 <= Math.square(n) всегда верно.

Answer 14

Чтобы проверить простоту числа, 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 не является простым числом, и в этот момент цикл завершается. Если для нет 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 (целое число)

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

Кроме того, n/k = a, и, как указано выше, a является значением i, поэтому n > a > 1.

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

Другими словами, если бы тест на простоту n был неудачным для некоторого i >= sqrt(n) (то есть max(a,k)), то он также не прошел бы для некоторого i <= n (то есть min (a), к)). Таким образом, будет достаточно, если мы запустим тест для i = 2 до sqrt (n).

Answer 15

      def print_hi(n):
if(n == 1 ):
    return False;
if( n == 2 or n == 3):
    return True;
if(n % 2 == 0 or n % 3 == 0):
    return  False;

for i in range (5,n,6):
    if( i * i <= n):
        if(n % i == 0 or n % (i+2) == 0):
            return False
        return True


if __name__ == '__main__':
  x = print_hi(1032)
  print(x)