Первичность числа
Известно, что для проверки, является ли число n простым или нет, нам просто нужно проверить, имеет ли он коэффициент меньше квадратного корня из n.
Мой вопрос не достаточно ли проверить все простые числа меньше, чем квадратный корень из n.
4 ответа
Каждое целое число n больше 1 либо является простым числом, либо является произведением простых чисел (основная теорема арифметики). Таким образом, если n не является простым числом, оно должно делиться как минимум на два простых числа. По крайней мере, одно из них должно быть меньше или равно √n (иначе их произведение будет больше n), поэтому достаточно проверить все простые числа, меньшие или равные √n.
Да, нужно только проверить фактор меньше sqrt(n). Но этот алгоритм немного медленный. У меня есть еще один лучший алгоритм под названием Miller_Rabin_primality Мой предыдущий код проекта Исходный код
Вот вики
Мы можем спорить так:
Пусть номер для проверки будет n, Пусть будет номер k <= sqrt(n) который делит n, Теперь мы можем написать k следующее:
k = (p_1^a_1)(p_2^a_2)...(p_x^a_x)
где p_1, p_2, ..., p_x простое число меньше или равно k а также a_1, a_2, ..., a_x >= 1, Теперь, так как k водоразделы nи так как мы знаем, что p_1, p_2, ..., p_x водоразделы kпо транзитивности мы можем сделать вывод, что p_1, p_2, ..., p_x водоразделы n, Таким образом, чтобы доказать, что n не является простым, достаточно проверить, является ли какое-либо из простых чисел <= sqrt(n) водоразделы n или нет.
Да, то, что вы говорите, абсолютно правильно.
Вам просто нужно проверить все простые числа меньше, чем равно squareRoot(n), но дело в том, что вы не знаете, простое число или нет. Итак, вы проходите до squareRoot(n)