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

Предыдущий
вопрос Следующий
вопрос

Формула 2**n % n == 2 используется для проверки числа на простоту и базируется на малой теореме Ферма.

Малая теорема Ферма утверждает, что если p - простое число и a - целое число, не делящееся на p, то a^(p-1) ≡ 1 (mod p), где ≡ обозначает сравнимость по модулю.

Если применить эту теорему к формуле 2n % n == 2, то получится следующее:
2n % n == 2 можно переписать как 2n ≡ 2 (mod n).
Это означает, что если число n простое, то 2^(n-1) ≡ 1 (mod n) согласно малой теореме Ферма. Таким образом, если числа n простое, то 2(n-1) % n будет равно 1. Однако, если n не является простым числом, то равенство не будет выполняться.

Таким образом, формула 2**n % n == 2 позволяет определить простое число при минимальном количестве кода, используя свойства простых чисел и малую теорему Ферма.