Функция в С++ для проверки на простоту

234

29 июня 2018, 03:50

Существует ли функция в С++ в STL для проверки, является ли число простым, и если да, то где про нее почитать? (или просто шаблон дайте)

Answer 1

В стандарте, вроде, нет.

Проверить можно, например, простым алгоритмом в лоб: перебрать все нечетные числа от 3 до sqrt(N), проверяя, не являются ли они делителями. Можно сделать алгоритм более хитрым, добавив к этому нечто вроде решета Эратосфена: если 3 не является делителем N, то, очевидно, никакое кратное 3 тоже не будет, позволяет, вроде бы, уменьшить число делений — за счет запоминания, какие делители уже можно не проверять.

Это простые способы.