Формула для простых чисел?

Question

[Андрей]

Писал программу где необходимо было определить простое число при минимальном количестве кода, подсказали формулу : если 2**n%n ==2 то число простое, где ** - возведение в степень, а % - остаток от деления, может кто подсказать что лежит в основе формулы? (хотелось бы понять как это работает)

Answer 1

[Пума Тайланд]

А смысл, как вы будете возводить в степень хотя бы миллион, обычно проще всего иметь готовую матрицу простых чисел, тогда кода будет всего одна строчка сравнения

Comments

[bobrovskyserg]

Возведение в степень по модулю - очень дешевая операция.