Чтобы найти число простое, почему проверка до п /2 лучше. В чем причина избегания чисел во второй половине дня?
Чтобы проверить, является ли число простым или нет, наивным способом является попытка разделить число на 2 через n, и если какая-либо операция получает остаток как 0, то мы говорим, что данное число не простое. Но оптимально делить и проверять только до n/2 (я знаю, что гораздо лучше до sqrt(n)), я хочу знать причину пропуска второй половины.
скажем, нужно ли нам проверять число 11 простое или нет, 11/2 = 5. если мы делаем 11/6, или 11/7, или 11/8, или 11/9, или 11/10, ни в одном из этих случаев мы не получим остаток как 0. Так обстоит дело для любого данного числа п.
Является ли причиной избежать второй половины этого? "если вы разделите данное число на любое число, которое больше половины данного числа, остаток никогда не будет равен 0. Другими словами, ни одно из чисел, которые больше половины данного числа, не сможет разделить данное число"
Пожалуйста, помогите мне знать, если я прав
5 ответов
Потому что наименьшее кратное число, которое не сделает его простым, равно 2. Если вы проверили все числа от 0 до n/2, какое еще множитель может сработать? Если кратное 2 больше n, то кратное 3 или 4 и т. Д. Также будет больше n.
Таким образом, самый большой коэффициент для любого числа N должен быть <= N/2
Так что да, возьмите N / 2 и проверьте все целые числа, меньшие или равные N/2. Таким образом, для 11 вы должны проверить все целые числа меньше 5,5, то есть 1, 2, 3, 4 и 5.
Здесь объясняется квадратный корень: почему мы проверяем квадратный корень из простого числа, чтобы определить, является ли оно простым?
И этот вопрос был задан ранее.
Чтобы рассчитать число n Вы должны разделить на два других целых числа, назвать их a а также b, Оба эти числа должны быть 2 или больше, поэтому нет смысла проверять числа больше n/2они не могли бы делить равномерно.
И да, sqrt(n) более эффективен, потому что если a больше чем sqrt (n) тогда b должно быть меньше, и вы бы уже проверили это.
давайте возьмем число n... конечно, если это натуральное число и не простое, это будет умножение 2 чисел... скажем, числа равны a и b, поэтому n=a b...где n >1 Чтобы определить, является ли число n простым... ab оба должны быть больше или равны 2 и короче самого n... Итак, наименьшее значение как a, так и b может быть равно 2... давайте скажем, b=2... n=ab.. =>n=a2 (принимая b=2...) =>n/2=(a2)/2 (делим 2 в обе стороны) =>a=n/2...
Итак, для того, чтобы b было наименьшим 2, a может быть самым высоким n/2, чем больше a становится больше, чем n/2... чем больше b становится меньше 2... но это нарушает правило... вот почему мы проверяем, делится ли оно на 2 или n/2, чтобы определить, является ли число простым или нет...
Эй, я застрял с тем же вопросом, и я понял кое-что простое, что, вероятно, отвечает на этот вопрос. Мы можем заметить, что для каждого четного целого числа n второй старший фактор всегда равен n/2, а для каждого нечетного целого числа n второй старший фактор всегда меньше n/2. Таким образом, мы получаем представление о том, что для проверки того, является ли число простым или нет, нам нужно проверить делимость этого числа только до n/2, потому что после n/2 самым следующим множителем является само число. Так что это пустая трата времени, чтобы просто проверить вторую половину, где фактор не может присутствовать.
Теперь, почему n/2 играет ключевую роль? Предположим, что n=a*b; где a & b — множители n. У нас может быть два случая: либо a=2 (в случае, если «n» четно), либо a=k (в случае, если «n» нечетно, где «k» — любое число> 2).
имеем b=n/a;
Таким образом, b либо равно n/2 (если n четно, то a=2), либо
b=n/k (где k>2). Так как k>2, b<n/2
Отсюда мы можем ясно заключить, что b всегда будет меньше или равно n/2.
Цель - показать, что множители составного числа (за исключением 1 и самого числа) принадлежат множеству {2, 3, 4, 5, 6....., [n / 2]}, где [] обозначает Наибольшая целочисленная функция.
Доказательство:
Предположим, что составное число равно n. Пусть это будет выражено как произведение двух множителей a, b (оба не равны 1 или n, поскольку мы точно знаем, что 1 и n будут делить n, поэтому наименьшее натуральное число, которое могут быть a и b, равно 2).
n=a x b
Предположим, что a>[n / 2].
Then b=n/a this implies that b<2
(например, предположим, что n=39, тогда a>[39/2]=19. Предположим, что a равно 20 (что больше 19), тогда b = 39/20 = 1,95, что невозможно для наименьшего возможного значения как для a, так и для b. оба будут равны 2 (согласно нашему предположению), поскольку условия не выполняются для a = 20, дальнейшее увеличение a сделает b меньше и меньше 2. Таким же образом процесс мышления может быть расширен для всех составных чисел!)
Это невозможно, поскольку наименьшее натуральное число a и b может быть равно 2.
Следовательно, наше предположение было неверным, следовательно, a и b оба должны принадлежать множеству {2, 3, 4, 5, 6....., [n / 2]}.