Вход
Быстрая регистрация
Если вы у нас впервые: О проекте FAQ
1

Как наиболее эффективно проверить, что число простое?

Esketit [7.4K] более года назад
0

Натуральное число, не равное единице, является простым, если оно имеет ровно два делителя: единица и само это число. Таким образом, нам достаточно проверить, есть ли в интервале от единицы до нашего числа хотя бы один делитель. Наиболее эффективно сделать это можно, перебрав все нечётные делители и двойку. При этом перебор можно закончить, как только мы дойдём до корня нашего числа, потому что если мы не нашли искомый делитель до корня, то и после корня его не будет.

модератор выбрал этот ответ лучшим
0

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

Знаете ответ?
Есть интересный вопрос? Задайте его нашему сообществу, у нас наверняка найдется ответ!
Делитесь опытом и знаниями, зарабатывайте награды и репутацию, заводите новых интересных друзей!
Задавайте интересные вопросы, давайте качественные ответы и зарабатывайте деньги. Подробнее..
регистрация