Найдите простое число?

Question

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

Answer 1

N является простым, если оно является положительным целым числом, которое делится ровно два положительными целыми числами, 1 и N. Так как делители целого ряда не может быть больше, чем это число, это приводит к простому тесту на простоту:

• Если целое число N, большее 1, не делится никаким целым числом в диапазоне [2, N-1], тогда N является простым. В противном случае N не является простым.

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

Обратите внимание, что делители N встречаются попарно. Если N делится на число M, то оно также делится на N/M. Например, 12 делится на 6, а также на 2. Кроме того, если M >= sqrt(N), то N/M <= sqrt(N).

Это означает, что если числа, меньшие или равные sqrt (N), не делят N, числа, большие, чем sqrt (N), не делят N ни (кроме 1 и N), в противном случае возникло бы противоречие.

Итак, мы имеем лучшее испытание:

• Если целое число N, больше, чем 1, не делится на любое целое число в диапазоне [2, sqrt(N)], то N является простым. В противном случае N не является простым.

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

Answer 2

Совокупное число (одно, которое не является простым или 1) имеет не менее 1 пары факторов, и гарантируется, что одно из чисел из каждой пары меньше или равно квадратному корню из числа (о чем вы спрашиваете).

Если вы нажмете квадратный корень номера, вы получите номер (sqrt(n) * sqrt(n) = n), поэтому, если вы сделали один из чисел больше (чем), вам нужно было бы сделать другое меньшим. Если вы только проверите номера с 2 по sqrt(n), вы проверите все возможные факторы, так как каждый из этих факторов будет сопряжен с числом, которое больше sqrt(n) (за исключением, конечно, если число фактически является квадратом некоторых другое число, например 4, 9, 16 и т. д., но это не имеет значения, поскольку вы знаете, что они не простые, они легко учитываются самим sqrt(n)).

Answer 3

Потому что в худшем случае номер n может быть представлен как .

Если число может быть выражено разным, то мужчины, что один из делителей будет меньше a = sqrt(n), а другой может быть больше.

Answer 4

Причина проста, любое число, большее, чем sqrt, приведет к тому, что другой множитель будет меньше, чем sqrt. В таком случае вы должны это проверить.

Answer 5

Пусть п = × б быть составным.

Предположим > SQRT (п) и б> SQRT (п).

× б> SQRT (п) × SQRT (п)

× б>п

Но мы знаем, × b = n, поэтому < SQRT (п) или б < SQRT (п).

Так как вам нужно знать только или б показать п составной, вам нужно только проверить номера до SQRT (п), чтобы найти такое число.