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

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

330 голосов
/ 28 апреля 2011

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

Ответы [ 13 ]

1 голос
/ 24 января 2016

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

0 голосов
/ 18 декабря 2018

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

Скажем, n = p1 * p2, где p2 > p1, и они являются простыми числами.

Если n % p1 === 0, то n является составным числом.

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

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

0 голосов
/ 29 июня 2017

Для проверки простоты числа, 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 (то есть мин (а, к)). Таким образом, будет достаточно, если мы запустим тест для i = 2 до sqrt (n). </p>

Страница:
...