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

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

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

...

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

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

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

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

...

Answer 8

Итак, чтобы проверить, является ли число N основным или нет. Нам нужно только проверить, делится ли N на числах <= sqroot (n). Это потому, что, если мы учитываем n в любые 2 фактора, говорят x и y, т. Е. N = xY. Каждый из x и y не может быть меньше, чем sqroot (n), потому что тогда, xY <n Каждый из x и y не может быть больше, чем sqroot (n), потому что тогда, x*y> n

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

Answer 9

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

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

Так что теперь, если «а» не является ярким, его можно разделить на два других числа, и, скажем, эти цифры «B» и «C». Что значит

a = b*c.

Теперь, если «B» или «C», любой из них больше, чем квадратный корень «A», чем умножение «B» и «C», будет больше, чем «A».

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

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

Answer 10

Пусть n не присваивается. Следовательно, он имеет как минимум два целочисленных фактора, превышающих 1. Пусть F является самым маленьким из таких факторов N. Предположим, f> sqrt n. Тогда N/F является целочисленным SQRT N, таким образом, меньше f. Следовательно, F не может быть самым маленьким фактором N. Reductio Ad Absurdum; Наименьший фактор N должен быть SQRT n.

Answer 11

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

sqrt(n) = p

Конечно, если мы размножаемся p сами по себе мы возвращаемся n:

p*p = n

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

a*b = n

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

Answer 12

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

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

Что делает вышеупомянутый цикл следующим образом: для данного 1 <я <n, он проверяет, является ли n/я целым числом (оставляет остаток 0). Если существует I, для которого N/I является целым числом, то мы можем быть уверены, что N не является основным числом, после чего петля заканчивается. Если нет, я/я является целым числом, то n является ярким.

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

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

Последовательность I Gos: 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 So N> a> 1.

Таким образом, A и K являются целыми числами от 1 до N (исключительно). Поскольку я достигаю каждого целого числа в этом диапазоне, на некоторых итерации i = a и на какой -то другой итерации i = k. Если тест первичности n не пройдет в течение мин (a, k), он также не удастся для максимума (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 , k)). Таким образом, было бы достаточно, если бы мы запустили тест для i = 2 до sqrt (n).

Answer 13

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

Давайте скажем n = p1 * p2, куда p2 > p1 И это простые числа.

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

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

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